No of Factors of n! - GeeksforGeeks

No of Factors of n! - GeeksforGeeks
Given a positive integer n, find the no of factors in n! where n <= 10⁵.

Note that the brute force approach won’t even work here because we can’t find n! for such large n. We would need a more realistic approach to solve this problem.

Any positive integer can be expressed as product of power of its prime factors. Suppose a number n = p1a1 x p2a2x p3a3, …., pkak where p1, p2, p3, …., pk are distinct primes and a1, a2, a3,………….., ak are their respective exponents.
Then the no of divisors of n = (a1+1) x (a2+1) x (a3+1)…x (ak+1)

Thus, no. of factors of n! can now be easily computed by first finding the prime factors till n and then calculating their respective exponents.

The main steps of our algorithm are:

1. Iterate from p = 1 to p = n and at each iteration check if p is prime.
2. If p is prime then it means it is prime factor of n! so we find exponent of p in n! which is
3. After finding the respective exponents of all prime factors let’s say they are a1, a2 , a3, …., ak then the factors of n! = (a1+1) x (a2+1) x (a3+1)……………(ak+1)

Prime factors of 16! are: 2,3,5,7,11,13

Now to the exponent of 2 in 16!  
              = ⌊16/2⌋ + ⌊16/4⌋ + ⌊16/8⌋ + ⌊16/16⌋ 
              = 8+4+2+1=13

Similarly, 
   exponent of 3 in 16! =  ⌊16/3⌋ + ⌊16/9⌋ = 6
   exponent of 5 in 16! = 3 
   exponent of 7 in 16! = 2
   exponent of 11 in 16! = 1
   exponent of 13 in 16! = 1

So, the no of factors of 16! 
         = (15+1) * (6+1) * (2+1) * (1+1) * (1+1)
         = 5376 

void sieve(int n, bool prime[])

{

    // Initialize all numbers as prime

    for (int i=1; i<=n; i++)

        prime[i] = 1;

 

    // Mark composites

    prime[1] = 0;

    for (int i=2; i*i<=n; i++)

    {

        if (prime[i])

        {

            for (int j=i*i; j<=n; j += i)

                prime[j] = 0;

        }

    }

}

 

// Returns the highest exponent of p in n!

int expFactor(int n, int p)

{

    int x = p;

    int exponent = 0;

    while ((n/x) > 0)

    {

        exponent += n/x;

        x *= p;

    }

    return exponent;

}

 

// Returns the no of factors in n!

ll countFactors(int n)

{

    // ans stores the no of factors in n!

    ll ans = 1;

 

    // Find all primes upto n

    bool prime[n+1];

    sieve(n, prime);

 

    // Multiply exponent (of primes) added with 1

    for (int p=1; p<=n; p++)

    {

        // if p is a prime then p is also a

        // prime factor of n!

        if (prime[p]==1)

            ans *= (expFactor(n, p) + 1);

    }

 

    return ans;

}

Note : If the task is to count factors for multiple input values, then we can precompute all prime numbers upto the maximum limit 105.

Read full article from No of Factors of n! - GeeksforGeeks