Эффективное вычисление общего числа делителей целых чисел в диапазоне

Question

Учитывая диапазон [1, 2 миллиона], для каждого числа в этом диапазоне мне нужно сгенерировать и сохранить количество делителей каждого целого в массиве.

Таким образом, если х = p1^(а1) * p2^a2 * р3^a3, где p1, p2, p3 простые числа, общее число делителей х задается формулой (p1 + 1) (p2 +1) (p3 + 1). Я генерировал все простые числа ниже 2000 и для каждого целого числа в диапазоне, я делал пробное деление , чтобы получить мощность каждого простого коэффициента, а затем использовал приведенную выше формулу для вычисления числа делителей и хранился в массиве. Но это происходит довольно медленно и занимает около 5 секунд, чтобы сгенерировать количество divsors для всех чисел в заданном диапазоне.

Можем ли мы сделать эту сумму каким-либо другим эффективным способом, может быть, без факторизации каждого номера ?

Ниже приведен код, который я использую сейчас.

typedef unsigned long long ull; 
void countDivisors(){ 
    ull PF_idx=0, PF=0, ans=1, N=0, power; 
    for(ull i=2; i<MAX; ++i){ 
     if (i<SIEVE_SIZE and isPrime[i]) factors[i]=2; 
     else{ 
     PF_idx=0; 
     PF=primes[PF_idx]; 
     ans=1; 
     N=i; 
     while(N!=1 and (PF*PF<=N)){ 
      power = 0; 
      while(N%PF==0){ N/=PF; ++power;} 
      ans*=(power+1); 
      PF = primes[++PF_idx]; 
     } 
     if (N!=1) ans*=2; 
     factors[i] = ans; 
     } 
    } 
} 

Answer 1

Прежде всего, ваша формула неверна. Согласно вашей формуле сумма делителей 12 должна быть 12. На самом деле это 28. Правильная формула - (p1a1 - 1)*(p2a2 - 1) * ... * (pkak - 1)/((p1 - 1) * (p2 - 1) * ... * (pk - 1)).

Тем не менее, самый простой подход - это, вероятно, просто сделать сито. Можно быть умным с смещениями, но для простоты просто создайте массив из 2 000 001 целых чисел от 0 до 2 миллионов. Инициализируйте его до 0s. Затем:

for (ull i = 1; i < MAX; ++i) { 
    for (ull j = i; j < MAX; j += i) { 
     factors[j] += i; 
    } 
} 

Это может показаться неэффективным, но это не так уж плохо. Суммарная работа по номерам до N составляет N + N/2 + N/3 + ... + N/N = O(N log(N)), что на несколько порядков меньше пробного деления. И все операции - это дополнение и сравнение, которые бывают быстрыми для целых чисел.

Если вы хотите продолжить свою оригинальную идею и формулу, вы можете сделать это более эффективным, используя модифицированное сито Eratosthenes, чтобы создать массив от 1 до 2 миллионов, указав простой коэффициент каждого числа. Построение этого массива довольно быстро, и вы можете использовать любое количество и факторизовать его гораздо быстрее, чем вы могли бы с пробным делением.