Улучшите код, который факторизуется быстрее?

Question

Я хотел бы сделать этот фрагмент кода быстрее. Он возвращает все факторы (простые числа) длинного числа. Очевидно, что минуты должны быть выполнены, если longNumber является конкретным.

int div = 2; 
String factors = ""; 

while (longNumer != 1) 
{ 
    if (longNumer % div == 0) 
    { 
     longNumer /= div; 
     factors += div + " "; 
    } 
    else { div++; } 
} 

//longNumber = 10, gives: 2 5. 
//longNumber = 150, gives: 3 5 7. 
//longNumber = 10523, gives: 17 619. 

Это занимает слишком много времени с номерами таких «7544222046562688368», и это не очень хорошо, что вы могли бы предложить?

Answer 1

Вы можете использовать следующие шаги вместо -

1. Найти все простые числа < = SQRT (longNumber). И сохраните их в массиве - primes.
2. Теперь постепенно используйте элемент массива - primes в качестве делителя, чтобы найти коэффициент.

Answer 2

Для больших чисел можно использовать Sieve of Eratosthenes algorithm сначала найти простые числа до SQRT (п), а затем вы должны проверить, что ли эти простые числа факторов

Answer 3

Ответы предполагающие решета Эратосфена не делайте много для чисел, как вы описываете. Для 64 бит номеров sqrt(2^64) = 2^32, которого все еще много.

Для тех, ваши лучшие ставки Pollard's Rho algorithm или более сложные методы целочисленной факторизации перечислены here:

алгоритмы факторизации Алгебраическая-группы, среди которых р Полларда - 1 алгоритм, Williams' р + 1 алгоритм, и факторизация с помощью эллиптических кривых

метод факторизации Ферма

метод факторизации Эйлера

Специальное поле номер сито

Answer 4

Хороший способ к фактору 64-разрядных целых чисел, это как просто программировать и достаточно эффективно на практике, сочетает в себе пробное деление и алгоритм ро Полларда. Вот псевдокод:

function factors(n) 
    wheel := [1,2,2,4,2,4,2,4,6,2,6] 
    w, f, fs := 0, 2, [] 
    while f*f <= n and f < 10000 
     while n % f == 0 
      fs, n := f :: fs, n/f 
     f, w := f + wheel[w], w+1 
     if w = 11 then w = 3 
    if n == 1 return fs 
    h, t, g, c := 1, 1, 1, 1 
    while not isPrime(n) 
     repeat 
      h := (h*h+c) % n # the hare runs 
      h := (h*h+c) % n # twice as fast 
      t := (t*t+c) % n # as the tortoise 
      g := gcd(t-h, n) 
     while g == 1 
     if isPrime(g) 
      while n % g == 0 
       fs, n := g :: fs, n/g 
     h, t, g, c := 1, 1, 1, c+1 
    return n :: fs 

Это использует 2,3,5-колесо для пробного деления до 10000 с последующим простой реализацией алгоритма ро; он должен учитывать ваш номер образца как 7544222046562688368 = 2 * 2 * 2 * 2 * 7 * 7 * 14618561 * 658254407 через несколько миллисекунд. Усовершенствования возможны, но этого должно быть достаточно, чтобы вы начали.

Answer 5

Перед тем, как внедрить один из алгоритмов факторинга быстрее, чем пробное деление, одна легко исправленная ошибка состоит в том, чтобы избежать выполнения пробного деления за sqrt последней части.

while (longNumber != 1) { 
    if (longNumber % div == 0) { 
     longNumber /= div; 
     factors += div + " "; 
    } 
    else { 
     if (div*div>longNumber) { 
      if (longNumber > 1) 
       factors += longNumber + " "; 
      break; // leave the while loop. 
     } 
     div++; 
    } 
} 

Пусть два самых больших простых фактора - P1 и P2. В вашей версии вы выполняете операции c P1. В модифицированной версии вы делаете о c Max (sqrt (P1), P2). На 7544222046562688368 улучшение должно быть в 45 раз.

Другим усовершенствованием является изменение строки div ++. Вам не нужно делать пробное деление четными числами больше 2 или цифрами, делящимися на 3 больше, чем 3.Избегая этих ускорений вычислений более чем на 2%, и вы можете сделать несколько лучше, избегая тестирования кратных других небольших простых чисел. Тем не менее, вы не хотите тратить время на пробные подразделения div на небольшие простые числа. Вместо этого вы отслеживаете текущие и допустимые остатки mod 2 * 3 * 5 * 7, скажем. Это называется использованием колеса для небольших простых чисел.

Некоторые другие ответы говорят о том, чтобы использовать сито, чтобы найти все мелкие простые числа, а затем использовать пробное деление только этими. Это не поможет, если вы факторизуете только одно число, так как слишком долго приходится просеивать простые числа. Получение списка простых чисел до sqrt (n) занимает около c sqrt (n) loglog n операций, а пробное деление на все до sqrt (n) занимает около c sqrt (n) операций. Выполнение сита один раз и сохранение результатов может помочь, если вам нужно учитывать множество больших чисел.