我必须找到给定数字 N 的除数总数,其中可以大到 10^14。我尝试计算素数到 10^7,然后使用素数因子的指数找到除数。但是结果太慢了,因为使用筛子找到素数需要 0.03 秒。如何在不计算素数的情况下更快地计算除数的总数?请伪代码/很好解释的算法将不胜感激。
问问题
4602 次
3 回答
4
使用阿特金筛法找出所有小于 10^7 的素数。(其中有 664,579 个)
http://en.wikipedia.org/wiki/Sieve_of_Atkin
理想情况下,这应该在编译时完成。
接下来计算素数分解:
int x; // the number you want to factor
Map<int to int> primeFactor; // this is a map that will map each prime that appears in the prime factorization to the number of times it appears.
while(x > 1) {
for each prime p <= x {
if x % p == 0 {
x = x / p;
primeFactor(p) = primeFactor(p) +1;
}
}
}
最后,您将获得完整的素数分解。由此,您可以通过迭代地图的值来计算除数的总数: https ://math.stackexchange.com/questions/66054/number-of-combinations-of-a-multiset-of-objects
int result = 1;
for each value v in primeFactors {
result*= (v+1);
}
于 2012-09-05T20:12:16.037 回答
1
您可以使用Pollard 的 rho 算法进行因式分解。有了所有的改进,至少 10^20 的数字很快。
这是我在 Java 中查找因子的实现:
/**
* Finds a factor of a number using Brent's algorithm.
*
* @param n The number.
*
* @return A factor of n.
*/
public static BigInteger findFactor(BigInteger n)
{
final BigInteger result;
if (n.isProbablePrime(80))
{
result = n;
}
else
{
BigInteger gcd = n;
BigInteger c = ONE;
while (gcd.equals(n))
{
int limitPower = 0;
long k = 0;
BigInteger y = ONE;
boolean done = false;
while (!done)
{
limitPower++;
final long limit = Numbers.pow(2, limitPower);
final int productLimit = (int) Numbers.pow(2, limitPower / 2);
final BigInteger x = y;
while (!done && k < limit)
{
final BigInteger savedY = y;
int j = 0;
final int jLimit = (int) Math.min(productLimit, limit - k);
BigInteger p = ONE;
while (j < jLimit)
{
y = next(n, c, y);
p = p.multiply(x.subtract(y)).mod(n);
j++;
}
gcd = Numbers.gcd(p, n);
if (gcd.equals(ONE))
{
// Move along, nothing to be seen here
k += jLimit;
}
else
{
// Restart and find the factor
y = savedY;
while (!done)
{
k++;
y = next(n, c, y);
gcd = Numbers.gcd(x.subtract(y), n);
done = !gcd.equals(ONE);
}
}
}
}
c = c.add(ONE);
}
result = gcd;
}
return result;
}
private static BigInteger next(BigInteger m, BigInteger c, BigInteger x)
{
return square(x).subtract(c).mod(m);
}
要分解最多 10 14的数字,您也可以对最多 10 7的奇数进行试除法。
于 2012-09-23T06:51:28.827 回答