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

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

1 голос
/ 07 февраля 2012

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

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

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

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

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

1 Ответ

3 голосов
/ 07 февраля 2012

Прежде всего, ваша формула неверна. Согласно вашей формуле, сумма делителей 12 должна быть 12. На самом деле это 28. Правильная формула (p<sub>1</sub><sup>a<sub>1</sub></sup> - 1)*(p<sub>2</sub><sup>a<sub>2</sub></sup> - 1) * ... * (p<sub>k</sub><sup>a<sub>k</sub></sup> - 1)/( (p<sub>1</sub> - 1) * (p<sub>2</sub> - 1) * ... * (p<sub>k</sub> - 1) ).

Тем не менее, самый простой подход, вероятно, просто сделать сито. Можно сообразить со смещениями, но для простоты просто создайте массив из 2000 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)), что на несколько порядков меньше, чем пробное деление. И все операции - сложение и сравнение, которые быстры для целых чисел.

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

...