Как я могу написать быструю функцию для вычисления общего делителя числа?
Я должен найти общее число делителей данного числа N, которое может достигать 10 ^ 14. Я попытался вычислить простые числа до 10 ^ 7, а затем найти делители, используя показатели простых множителей. оно оказывается слишком медленным, так как нахождение простых чисел с помощью сита занимает 0,03 с. Как можно быстрее вычислить общее число делителей и, если возможно, без вычисления простых чисел? Пожалуйста, псевдокод / хорошо объясненный алгоритм будет с благодарностью.
Решение
Используйте сито Аткина, чтобы найти все простые числа менее 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);
}
Другие решения
Я реализовал Сито Аткина на моем блог, но все же нашел оптимизированное сито эратосфена быстрее.
Но я сомневаюсь, что это твоя проблема. Для чисел, больших 10 ^ 14, факторизация Полларда превзойдет пробное деление на простые числа, независимо от того, как вы генерируете простые числа. Я сделал это на моем блог, тоже.
Ты можешь использовать Ро-алгоритм Полларда для факторизации. Со всеми улучшения это быстро для чисел не менее 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);
}
Разложить числа до 1014 Вы также можете просто сделать пробное деление с нечетными числами до 107.