Эффективная Prime Factorization для больших чисел

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

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

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

Поэтому я рекомендую разбить сито на сегменты, которые поместятся в кэш 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.

Кстати, результаты, которые я получаю на скромном AMD Phenom II x6 1090T (8 МБ кэш-памяти L3), для простых чисел до 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 МБ кэш-памяти L3 одновременно.

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

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

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

Простое ускорение двух может быть легко достигнуто путем изменения вашего цикла:

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 МБ памяти. Этот алгоритм является классическим решением SPOJ проблема № 2, 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. E-mail: [email protected]