Эффективная факторизация простых чисел для больших чисел

Пробное деление подходит только для факторинга небольших чисел. Для n до 2 ^ 64 вам понадобится лучший алгоритм: я рекомендую начать с факторизации колеса, чтобы получить малые множители, а затем алгоритм rho Полларда, чтобы получить остальное. Если пробное деление - O (sqrt (n)), rho - O (sqrt (sqrt (n))), так что это намного быстрее. Для 2 ^ 64 sqrt (n) = 2 ^ 32, но sqrt (sqrt (n)) = 2 ^ 16, что является огромным улучшением. Вы должны рассчитывать на факторизацию ваших чисел максимум за несколько миллисекунд.

У меня нет кода C ++ для факторинга, но у меня есть читаемый код Python. Дайте мне знать, если вы хотите, чтобы я опубликовал это. Если вы хотите узнать больше о факторизации колес и алгоритме rho, у меня есть много информации о простых числах в моем блоге.

Я обнаружил, что Сито Эратосфена на вашем современном процессоре забивает кэш, поэтому пропускная способность основной памяти является ограничивающим фактором. Я обнаружил это, когда пытался запустить несколько потоков и не смог ускорить работу настолько, насколько я надеялся.

Итак, я рекомендую разбить решето на сегменты, которые поместятся в кеш L3. Кроме того, если вы исключите из битового вектора числа, кратные 2, 3 и 5, тогда 8-битный байт может представлять 30 чисел в числовой строке, с 1 битом для каждого числа, которое равно 1, 7, 11, 13, 17, 19. , 23 или 29 по модулю 30 - так что битовая карта для простых чисел до 10 ^ 9 занимает ~ 32 МБ - 10 ^ 9 / (30 * 1024 * 1024). Это почти половина размера битовой карты, которая просто исключает кратные 2, что составляет ~ 60 МБ - 10 ^ 9 / (2 * 8 * 1024 * 1024).

Очевидно, что для запуска сита до 10 ^ 9 вам понадобятся простые числа до sqrt (10 ^ 9), что требует около 1055 байтов, из которых вы можете сгенерировать любую часть полного сита до 10 ^ 9.

FWIW, результаты, которые я получаю на скромном AMD Phenom II x6 1090T (кэш L3 8 МБ), для простых чисел до 10 ^ 9 следующие:

  1. 1 core,   1 segment    3.260 seconds elapsed
  2. 5 cores,  1 segment    1.830 seconds elapsed
  3. 1 core,   8 segments   1.800 seconds elapsed
  4. 5 cores, 40 segments   0.370 seconds elapsed

где под сегментом я подразумеваю часть сита. В этом случае размер сита составляет ~ 32 МБ, поэтому при наличии нескольких сегментов они одновременно используют около 4 МБ кеш-памяти третьего уровня.

Это время включает время, необходимое для сканирования заполненного сита и генерации всех простых чисел в виде массива целых чисел. Это занимает около 0,5 секунды процессора! Таким образом, для запуска сита без фактического извлечения из него простых чисел требуется 0,270 секунды в случае (4) выше.

FWIW, я получаю небольшое улучшение - до 0,240 секунды в случае (4) - за счет инициализации каждого сегмента с использованием предварительно вычисленного шаблона, который удаляет кратные 7, 11, 13 и 17. Этот шаблон составляет 17 017 байт.

Понятно, что для однократной факторизации за 0,06 секунды ... вам нужно, чтобы сито было предварительно вычислено!

for(int i  = 2; i * i <= n; ++i) //no sqrt, please
{
    while(n%i == 0) //while, not if
    {
         factors.push_back(i);
         n/=i;
    }
}
if(n != 1)
{
    factors.push_back(n);
}

По сути, это более изящная реализация вашего алгоритма. Его сложность равна sqrt N. Он будет работать довольно быстро даже для 18-значного числа, но только если все простые множители малы. Если это произведение двух больших простых чисел или, что еще хуже, само простое число, это будет длиться примерно 10 секунд.

Простого ускорения в два раза можно легко добиться, изменив свой цикл:

if (n % 2) {
    return vec.push_back(i), getPrimes(n / i, vec);
}

for (int i = 3; i <= sqrt_of_n; i += 2)
{
    if (n % i == 0) 
    {
        return vec.push_back(i), getPrimes(n / i, vec); //cause recursion
    }
}

Сначала вы должны проверить число на два. Затем, начиная с 3, вы снова тестируете, увеличивая цикл на два за раз. Вы уже знаете, что 4, 6, 8, ... четные числа и имеют 2 в качестве множителя. Проверяя четные числа, вы вдвое уменьшаете сложность.

Чтобы разложить число N на множители, вам нужны только простые числа ‹= sqrt (N). Для 18-значного числа вам нужно только проверить все простые числа меньше 1e9, а поскольку имеется 98 миллионов простых чисел меньше чем 2e9, вы можете легко хранить 100 миллионов чисел на современных компьютерах и параллельно проводить факторинг. Если каждое число занимает 8 байтов ОЗУ (int64_t), 100 миллионов простых чисел потребуют 800 МБ памяти. Этот алгоритм является классическим решением проблемы № 2 SPOJ, Prime Generator.

Лучший способ составить список всех малых простых чисел, которые могут уместиться в 32-битном int, - это построить Sieve of Eratostenes. Я сказал вам, что нам нужны простые числа меньше sqrt (N), чтобы разложить на множители любое N, поэтому для разложения 64-битных целых чисел вам нужны все простые числа, которые подходят как 32-битное число.

Алгоритм:

1. Разделите число на 2, пока оно не станет на него делимым, сохраните результат и отобразите его.
2. Разделите число на 3, пока оно не станет делимым на 3, и отобразите результат,
3. Повторите тот же процесс для 5,7 ... и т. Д. До получения квадратного корня из n.

4. Если в конце результирующее число является простым, отобразите его количество как 1.

   int main() {
   long long n;
   cin >> n;
   int count =0 ;
   while(!(n%2)){
       n = n / 2;
       count++;
   }
   if(count > 0) {
       cout<<"2^"<<count<<" ";
   }
   for(long long i=3;i<=sqrt(n) ; i+=2){
       count=0;
       while(n%i == 0){
           count++;
           n = n/i;
       }
       if(count){
           cout << i <<"^" <<count<<" ";
       }
   
   }
   if(n>2){
       cout<<n <<"^1";
   }
   
   
   
   return 0;
   }
   

Вход: 100000000 Выход 2 ^ 8 5 ^ 8

Алгоритм факторизации целых чисел настолько прост, что его можно реализовать даже на счетах.

void start()
{ 
   int a=4252361;    //  integer to factorize
   int b=1,  c,  d=a-1;  

   while ((a > b) && (d != b))
  {
    if (d > b)
     {
       c=c+b;
       a=a-1;
       d=a-c-1;
     }
    if (d < b)
     {
       c=b-d;
       b=b+1;
       a=a-1;
       d=a-c-1;
     }         
  }
    if ((d == b)&&(a > b)) 
  Alert ("a = ",  a-1,  " * ", b+1); 

    if ((d < b)&&(a <= b)) 
  Alert ("a  is a prime");

  return;
}

Алгоритм составлен мной, Миляевым Виктором Константиновичем, 26 июля 1950 года рождения. Написан на языке MQL4 15.12. 2017. Электронная почта: [email protected]