Каков наилучший алгоритм для определения числа факторов первых N натуральных чисел?

Question

Я должен найти общее количество факторов для всех чисел из 2 to N,

Вот мой подход.

Бежать Sieve of Eratosthenes и получить все простые числа от 2 to N,

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

N = 2^x1 * 3^x2 * 5*x^3 ...

Затем,

Number of factors = (x1 + 1) * (x2 + 1) * (x3 + 1) ...

Есть ли альтернативный / эффективный способ, которым я могу эффективно рассчитать общее количество факторов для первого N натуральные числа.

Answer 1

Число факторов всех целых чисел от 2 до N можно рассчитать в O(N) по следующей формуле:

total = N/1 + N/2 + ... + N/N - 1. (integer division)

Любое конкретное целое число x между 2 и N является множителем следующих целых чисел между 2 и N: x, 2x, 3x, 4x, ..., (N/x)x

Пример 1, общее число факторов чисел от 2 до 6 составляет 13: 6/1 + 6/2 + 6/3 + 6/4 + 6/5 + 6/6 - 1 = 6+3+2+1+1+1-1 = 13

These are the factors:
2: 1, 2
3: 1, 3
4: 1, 2, 4
5: 1, 5
6: 1, 2, 3, 6

2, 3, and 5 all have 2 factors, 4 has 3, and 6 has 4, for a total of 13.

Если вы просто хотите основные факторы:

total = N/p1 + N/p2 + ... + N/pk where pk is the largest prime <= N.

Например, N=6: 6/2 + 6/3 + 6/5 = 6

2: 2
3: 3
4: 2
5: 5
6: 2, 3