c++ - 寻找因素

Question

嗯，我正在做一个 C++ 程序，因为我需要从数组中找到具有公因数的数字。我已经在用天真的方式做这件事了。

int commonFactors(int p, int q){
    int count = 0;

    if(q > p){
        for(int i = 2;i < q;i++){
            if((q%i==0)&&(p%i==0)){
                count++;
                break;
            }
        }
    }
    else if(p > q){
        for(int i = 2;i < p;i++){
            if((p%i==0)&&(q%i==0)){
                count++;
                break;
            }
        }
    }
    else{
        count = 1;
    }

    return count;
}

那么我的代码会因较大的输入而超时。对于数组中的任何元素，我的输入范围是 1 到 1000000。关于如何有效计算它的任何线索？

我有一个只检查主要因素的想法，但我担心要检查的范围。

Answer 1

如果唯一的问题是“这两个是否有公因数(而不是一个公因数)”，那么一个选择就是计算它们的最大公约数，并检查它是否为一。使用 Euclidean algorithm 可以相当有效地计算 GCD(绝对比一直计算到你的数字要快) :

gcd(a, 0) = a
gcd(a, b) = gcd(b, a % b)