8

我正在用 C 编写一个代码，它返回一个正整数可以表示为两个正整数的完全平方和的次数。

R(n) is the number of couples (x,y) such that x² + y² = n where x, y, n are all 
non negative integers.

要计算 R(n)，我需要首先找到 n 的素数分解。

问题是我已经尝试了很多可以在 C 上使用的素数分解算法，但我需要我的代码尽可能快，所以如果有人能给我他/她认为的内容，我将不胜感激计算一个数的素数分解的最快算法2147483742.

4

2 回答 2

12

多么奇怪的限制；2147483742 = 2^31 + 94。

正如其他人所指出的那样，对于一个数字来说，这个小试除以素数很可能足够快。如果不是，您可以尝试 Pollard 的 rho 方法：

/* WARNING! UNTESTED CODE! */
long rho(n, c) {
    long t = 2;
    long h = 2;
    long d = 1;

    while (d == 1) {
        t = (t*t + c) % n;
        h = (h*h + c) % n;
        h = (h*h + c) % n;
        d = gcd(t-h, n); }

    if (d == n)
        return rho(n, c+1);
    return d;
}

调用 as ，此函数返回nrho(n,1)的（可能是复合的）因子；如果要查找n的所有因子，请将其放入循环中并重复调用它。您还需要一个素数检查器；对于您的极限，基于 2、7 和 61 的 Rabin-Miller 测试被证明是准确且相当快的。您可以在我的博客上阅读有关使用素数编程的更多信息。

但无论如何，鉴于如此小的限制，我认为你最好使用素数的试除法。其他任何东西都可能渐近更快，但实际上更慢。

编辑：这个答案最近收到了几个赞成票，所以我添加了一个简单的程序，用 2、3、5 轮进行轮子分解。称为wheel(n)，该程序按升序打印n的因子。

long wheel(long n) {
    long ws[] = {1,2,2,4,2,4,2,4,6,2,6};
    long f = 2; int w = 0;

    while (f * f <= n) {
        if (n % f == 0) {
            printf("%ld\n", f);
            n /= f;
        } else {
            f += ws[w];
            w = (w == 10) ? 3 : (w+1);
        }
    }
    printf("%ld\n", n);

    return 0;
}

我在我的博客上讨论了车轮分解；说明比较长，这里不再赘述。对于适合 a 的整数，long您不太可能显着改善wheel上面给出的函数。

于 2012-10-06T12:19:14.917 回答
1

有一种快速减少候选人数量的方法。这个例程尝试 2，然后是 3，然后是所有不能被 3 整除的奇数。

long mediumFactor(n)
{
    if ((n % 2) == 0) return 2;
    if ((n % 3) == 0) return 3;
    try = 5;
    inc = 2;
    lim = sqrt(n);
    while (try <= lim)
    {
       if ((n % try) == 0) return try;
       try += inc;
       inc = 6 - inc;  // flip from 2 -> 4 -> 2
    }
    return 1;  // n is prime
}

inc 在 2 和 4 之间的交替被仔细对齐，以便它跳过所有偶数和可被 3 整除的数字。对于这种情况：5 (+2) 7 (+4) 11 (+2) 13 (+4) 17

试验在 sqrt(n) 处停止，因为至少有一个因子必须等于或低于平方根。（如果两个因子都 > sqrt(n)，那么因子的乘积将大于 n。）

尝试次数为 sqrt(m)/3，其中 m 是您的系列中可能的最高数字。对于 2147483647 的限制，在最坏情况下（对于 2147483647 附近的素数）产生最多 15,448 个除法，包括 2 和 3 测试。

如果这个数字是复合的，那么分区的总数通常会少得多，而且很少会更多；甚至考虑到重复调用例程以获取所有因素。

于 2014-04-15T05:14:30.923 回答