在cpp中寻找两个数的LCM

Question

/Here，我为查找两个数字的LCM编写了代码，但我不知道为什么它不适用于9-10位数字。就像我给出的输入为245和922222222，那么它就不是工作，也不显示输出。

//代码如下

#include<iostream>
using namespace std;

long long product;

long long lcm(long long x,long long y){

    if(x>y)
        product=x;
    else
        product=y;

    while(1){
        if(product%x==0 && product%y==0){
            break;
        }
        product++;
    }

    return product;
}

int main(){
    cout<<lcm(245,922222222);
    return 0;
}

Answer 1

您的代码运行良好，需要几年时间才能完成。

你在浪费大量的时间检查数字，这不可能是结果。n % (n + 1)不可能是除1以外的任何n的0。通常，只有当n % (n + m)是n的倍数时，m才能成为n。这意味着您可以将更大的x和y添加到product的每个循环中，而不仅仅是1，并减少大量的工作量：

long long lcm(long long x,long long y) {

    long long greater = std::max(x, y);
    long long product = greater;

    while(product % x != 0 || product % y != 0) {
        product += greater;
    }

    return product;
}

演示

当然，即使是这样的工作也比您需要的要多，因为std::gcd存在：

long long lcm(long long x, long long y) {
    return x / std::gcd(x, y) * y;
}

演示

但这可能违反了任务的精神。