快速素数分解算法 [英] Fast Prime Factorization Algorithm
问题描述
我正在用C语言编写一个代码,该代码返回一个正整数可以表示为两个正整数的完美平方和的次数.
I'm writing a code in C that returns the number of times a positive integer can be expressed as sums of perfect squares of two positive integers.
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的素因式分解.
To compute R(n), I need to first find the prime factorization of n.
问题是我尝试了很多可以在C上使用的素因数分解算法,但是我需要我的代码尽可能快,所以如果有人可以给我他/她所提供的信息,我将不胜感激被认为是计算 2147483742之类的数字的素数分解的最快算法.
The problem is that I've tried a lot of algorithm for prime factorization that I can use on C but I need my code to be as fast as possible, so I would appreciate it if anyone can give me what he/she considers as the fastest algorithm to compute the prime factorization of a number as large as 2147483742.
推荐答案
真是个奇怪的限制;2147483742 = 2 ^ 31 + 94.
What an odd limit; 2147483742 = 2^31 + 94.
正如其他人所指出的那样,对于一个数字,这个很小的按质数的除法很有可能足够快.只有这样,您才可以尝试Pollard的rho方法:
As others have pointed out, for a number this small trial division by primes is most likely fast enough. Only if it isn't, you could try Pollard's rho method:
/* 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测试被证明是准确且相当快的.您可以在我的博客中阅读有关质数编程的更多信息.
Called as rho(n,1)
, this function returns a (possibly-composite) factor of n; put it in a loop and call it repeatedly if you want to find all the factors of n. You'll also need a primality checker; for your limit, a Rabin-Miller test with bases 2, 7 and 61 is proven accurate and reasonably fast. You can read more about programming with prime numbers at my blog.
但是在任何情况下,考虑到这么小的限制,我认为最好使用素数除法.其他任何事物可能在渐近上更快,但实际上更慢.
But in any case, given such a small limit I think you are better off using trial division by primes. Anything else might be asymptotically faster but practically slower.
该答案最近收到了几次投票,因此我要添加一个简单的程序,该程序车轮分解,带有2,3,5-车轮.称为 wheel(n)
,此程序按升序打印 n 的因子.
This answer has received several recent upvotes, so I'm adding a simple program that does wheel factorization with a 2,3,5-wheel. Called as wheel(n)
, this program prints the factors of n in increasing order.
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
函数.
I discuss wheel factorization at my blog; the explanation is lengthy, so I won't repeat it here. For integers that fit in a long
, it is unlikely that you will be able to significantly better the wheel
function given above.
这篇关于快速素数分解算法的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!