c - 快速素数分解算法

Question

我正在用 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 这样大的数字的质因数分解的最快算法。

Answer 1

多么奇怪的限制； 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;
}

调用为 rho(n,1)，此函数返回 n 的(可能是复合的)因子；如果你想找到 n 的所有因子，把它放在一个循环中并重复调用它。您还需要一个素数检查器；对于您的极限，以 2、7 和 61 为底的 Rabin-Miller 测试被证明是准确且相当快的。您可以在 my blog 阅读更多关于素数编程的信息。 .

但无论如何，考虑到如此小的限制，我认为您最好使用素数进行试验除法。其他任何东西都可能渐近地更快，但实际上更慢。

编辑:这个答案最近收到了几个赞成票，所以我添加了一个简单的程序来执行 wheel factorization带 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;
}

我在 my blog 讨论了车轮分解;解释很长，这里不再赘述。对于适合 long 的整数，您不太可能能够显着改善上面给出的 wheel 函数。