Каков наилучший алгоритм для определения числа факторов первых 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