CODEWITHSUNDEEP
algorithmmathdynamic-programmingmathematical-optimizationsieve-of-eratosthenes
Sai Nikhil
Sai Nikhil

Reputation: 1237

What is the best algorithm to find number of factors of first N natural numbers?

I have to find total number of factors for all numbers from 2 to N.

Here's my approach.

Run Sieve of Eratosthenes and get all primes from 2 to N.

For each number from 2 to N, do the prime factorisation and get the exponents of all the prime factors. Add 1 to each prime factor exponent and multiply all the exponents i.e.,

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

Then,

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

Is there any alternative/efficient way with which I can efficiently calculate total number of factors for first N natural numbers.

Upvotes: 4

Views: 1635

Answers (1)

Dave
Dave

Reputation: 9085

The number of factors of all integers between 2 and N can be calculated in O(N) via the following formula:

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

Any particular integer x between 2 and N is a factor of the following integers between 2 and N: x, 2x, 3x, 4x, ..., (N/x)x

Example 1, the total number of factors of the numbers from 2 to 6 is 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.

If you just want the prime factors:

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

E.g., N=6: 6/2 + 6/3 + 6/5 = 6

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

Upvotes: 6

Related Questions