我正在编写一段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 这样大的数字的质因数分解，我将不胜感激。
这个奇怪的限制是什么意思; 2147483742 = 2^31 + 94。
正如其他人所指出的，在这么小的数字范围内，通过质数试除法可能已经足够快了。只有当它不够快时，您可以尝试使用Pollard's 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测试已被证明准确且相当快速。您可以在我的博客上阅读更多有关使用质数进行编程的信息。
但无论如何，在给定这样一个小限制的情况下，我认为最好使用质数试除法。其他任何方法在渐近意义下可能更快，但实际上更慢。
编辑：由于此答案最近收到了多个赞，因此我正在添加一个简单的程序，它使用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;
}
我在我的博客上讨论了轮子分解；由于解释较长，因此我不会在这里重复。对于适合于long的整数，您很可能无法显着改进上述给出的wheel函数。
有一种快速的方式可以减少候选人的数量。这个程序会先尝试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的质数），包括2和3的测试，最多需要15448次除法。
如果数字是合数，则总除法次数通常要少得多，并且很少会更多；即使考虑到反复调用例程以获取所有因子。
public static IEnumerable<T> EnumeratePrimeFactors<T>(this T value) where T : IBinaryInteger<T>, IUnsignedNumber<T> {
if (BinaryIntegerConstants<T>.Four > value) { yield break; }
if (BinaryIntegerConstants<T>.Five == value) { yield break; }
if (BinaryIntegerConstants<T>.Seven == value) { yield break; }
if (BinaryIntegerConstants<T>.Eleven == value) { yield break; }
if (BinaryIntegerConstants<T>.Thirteen == value) { yield break; }
var index = value;
while (T.Zero == (index & T.One)) { // enumerate factors of 2
yield return BinaryIntegerConstants<T>.Two;
index >>= 1;
}
while (T.Zero == (index % BinaryIntegerConstants<T>.Three)) { // enumerate factors of 3
yield return BinaryIntegerConstants<T>.Three;
index /= BinaryIntegerConstants<T>.Three;
}
while (T.Zero == (index % BinaryIntegerConstants<T>.Five)) { // enumerate factors of 5
yield return BinaryIntegerConstants<T>.Five;
index /= BinaryIntegerConstants<T>.Five;
}
while (T.Zero == (index % BinaryIntegerConstants<T>.Seven)) { // enumerate factors of 7
yield return BinaryIntegerConstants<T>.Seven;
index /= BinaryIntegerConstants<T>.Seven;
}
while (T.Zero == (index % BinaryIntegerConstants<T>.Eleven)) { // enumerate factors of 11
yield return BinaryIntegerConstants<T>.Eleven;
index /= BinaryIntegerConstants<T>.Eleven;
}
while (T.Zero == (index % BinaryIntegerConstants<T>.Thirteen)) { // enumerate factors of 13
yield return BinaryIntegerConstants<T>.Thirteen;
index /= BinaryIntegerConstants<T>.Thirteen;
}
var factor = BinaryIntegerConstants<T>.Seventeen;
var limit = index.SquareRoot();
if (factor <= limit) {
do {
while (T.Zero == (index % factor)) { // enumerate factors of (30k - 13)
yield return factor;
index /= factor;
}
factor += BinaryIntegerConstants<T>.Two;
while (T.Zero == (index % factor)) { // enumerate factors of (30k - 11)
yield return factor;
index /= factor;
}
factor += BinaryIntegerConstants<T>.Four;
while (T.Zero == (index % factor)) { // enumerate factors of (30k - 7)
yield return factor;
index /= factor;
}
factor += BinaryIntegerConstants<T>.Six;
while (T.Zero == (index % factor)) { // enumerate factors of (30k - 1)
yield return factor;
index /= factor;
}
factor += BinaryIntegerConstants<T>.Two;
while (T.Zero == (index % factor)) { // enumerate factors of (30k + 1)
yield return factor;
index /= factor;
}
factor += BinaryIntegerConstants<T>.Six;
while (T.Zero == (index % factor)) { // enumerate factors of (30k + 7)
yield return factor;
index /= factor;
}
factor += BinaryIntegerConstants<T>.Four;
while (T.Zero == (index % factor)) { // enumerate factors of (30k + 11)
yield return factor;
index /= factor;
}
factor += BinaryIntegerConstants<T>.Two;
while (T.Zero == (index % factor)) { // enumerate factors of (30k + 13)
yield return factor;
index /= factor;
}
factor += BinaryIntegerConstants<T>.Four;
limit = index.SquareRoot();
} while (factor <= limit);
}
if ((index != T.One) && (index != value)) {
yield return index;
}
}
sqrt(2147483742)以内的所有质数的表格，并逐一尝试它们。这大约有6K个项目。 - Sergey Kalinichenko