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

Учитывая диапазон [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;
        }
    }
}

math prime-factoring
person praveen    schedule 06.02.2012    source источник

Ответы (1)


arrow_upward
3
arrow_downward

Во-первых, ваша формула неверна. По вашей формуле сумма делителей 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)), что на порядок меньше, чем пробное деление. И все операции сложения и сравнения, которые выполняются быстро для целых чисел.

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

person btilly    schedule 07.02.2012
comment
Спасибо за Ваш ответ. Прошу прощения, что задал неправильный вопрос. На самом деле мне нужно было количество делителей каждого целого числа меньше 2 миллионов. - person praveen; 07.02.2012
comment
@praveen Тогда просто factors[j]++; вместо factors[j] += i;. - person btilly; 07.02.2012