寻找因素

Question

好吧，我正在做一个 C++ 程序，因为我需要从一个 array.I 中找到具有公因数的数字，我已经用天真的方式做了。

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

您可以通过运行 for 循环更高效地完成 "sqrt(p)"（或 q，当然取决于较小的数字）。那应该已经加快了速度。

Answer 2

考虑两个数字：9240 和 16170。每个数字都可以记为（几个）质数的乘积：

9240 = 2*2*3*5*7*11
16170 = 2*3*5*7*7*11

从上面的示例可以明显看出，可能个公因子的总数就是您可以使用这些操作数创建的数字的总数列表。在这种情况下，数字集 2、3、5 和 11 将产生 15 总组合。

因此您的代码可以执行以下步骤（我不会为您编写 C++ 代码，因为您自己应该能够轻松完成）：

Split each the number into its prime factors using Integer factorization

Find the complete subset of those primes that are present in each list (don't forget that some may appear more than once in both lists and should be counted as separate ones, i.e. twice)

Find all the possible numbers you can create by combining the given set of primes

对于本文的最后一部分，您可以查看 Dynamic programming 与 naïve[=29] 相比，如何显着提高其性能的想法=]方法。

Answer 3

如果唯一的问题是 "do these two have a common factor (other than one)"，那么一个选项就是计算它们的最大公约数，并检查它是否是一个。使用 Euclidean algorithm:

可以相当有效地计算 GCD（绝对比一直数到你的数字要快）

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

Answer 4

首先是一些数学：假设A和B是两个正非空整数，让我们称C= gcd(A, B)为A和B的最大公约数，那么如果M同时整除A和B，则M除以 C.

所以如果你只想知道A和B是否有公约数你只需要检查C是否大于1，如果你想知道所有公约数（或他们的数字）你必须找到所有公约数C.

求两个数的GCD的欧几里德算法基于以下属性：假设B < A，A = P * Q + R是P除以Q的欧几里德除法，那么如果R = 0 , GCD(A,B) = B, 否则 GCD(A,B) = GCD(B,R) (ref wikipedia)

现在一些代码：

/* Euclidian algorythm to find Greatest Common Divisor
 Constraint (not controled here) p>0 and q>0 */
int gcd(int p, int q) {
    // ensures q < p
    if (p < q) {
        int temp = p;
        p = q;
        q = temp;
    }
    int r = p % q;
    // if q divises q, gcd is q, else gcd(p, q) is gcq(q, r)
    return (r == 0) ? q : gcd(q, r);
}

bool sharedivisors(int p, int q) {
    int d = gcd(p, q);
    return d > 1;
}

int divisors(int p, int q) {
    int d = gcd(p, q);
    if (d == 1) {
        return 1;
    }
    int count = 0;
    for(int i=2; i<d/2; i++) {
        if(d % i == 0) {
            int j = d/i;
            if (j > i) count += 2;
            else {
                if (j == i) count += 1;
                break;
            }
        }
    }
    return count + 2; // and 1 and d
}

Answer 5

计算从 2 到更大输入的因数是蛮力，即使其中一个输入很大，也能持续很长时间。公约数可以从其质因数分解的指数中获得。首先更容易计算出它们的最大公约数

gcd = gcd( p0, q0 )
/* .. */
int gcd( p0, q0 )
{
    while( q0 )
    {
        int swp = q0;
        q0 = p0 % q0;
        p0 = swp;
    }
    return p0;
}

然后计算它的除数

以天真的方式（如所讨论的那样）
始终将 gcd 除以找到的除数

通过质因数分解

p0^x0 * p1^x1 * .. * pN^xN = gcd
count = (1+x0) * (1+x1) * .. * (1+xN)

质因数分解需要最大为 sqrt(gcd) 的质数列表。

寻找因素

Finding factors

c++

factors