Как я могу написать быструю функцию для вычисления общего делителя числа?

Я должен найти общее число делителей данного числа N, которое может достигать 10 ^ 14. Я попытался вычислить простые числа до 10 ^ 7, а затем найти делители, используя показатели простых множителей. оно оказывается слишком медленным, так как нахождение простых чисел с помощью сита занимает 0,03 с. Как можно быстрее вычислить общее число делителей и, если возможно, без вычисления простых чисел? Пожалуйста, псевдокод / ​​хорошо объясненный алгоритм будет с благодарностью.

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);
}
4

Другие решения

Я реализовал Сито Аткина на моем блог, но все же нашел оптимизированное сито эратосфена быстрее.

Но я сомневаюсь, что это твоя проблема. Для чисел, больших 10 ^ 14, факторизация Полларда превзойдет пробное деление на простые числа, независимо от того, как вы генерируете простые числа. Я сделал это на моем блог, тоже.

1

Ты можешь использовать Ро-алгоритм Полларда для факторизации. Со всеми улучшения это быстро для чисел не менее 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.

1
По вопросам рекламы ammmcru@yandex.ru
Adblock
detector