Count Divisors of Factorial - GeeksforGeeks

Count Divisors of Factorial - GeeksforGeeks
Given a number n, count total number of divisors of n!.

A Simple Solution is to first compute factorial of given number, then count number divisors of the factorial. This solution is not efficient and may cause overflow due to factorial computation.

A better solution is based on Legendre’s formula . Below are the steps.

1. Find all prime numbers less than or equal to n (input number). We can use Sieve Algorithm for this. Let n be 6. All prime numbers less than 6 are {2, 3, 5}.
2. For each prime number p find the largest power of it that divides n!. We use below Legendre’s formula formula for this purpose.
   The value of largest power that divides p is ⌊n/p⌋ + ⌊n/(p2)⌋ + ⌊n/(p3)⌋ + ……
   Let these values be exp1, exp2, exp3,.. Using the above formula, we get below values for n = 6.
   • The largest power of 2 that divides 6!, exp1 = 4.
   • The largest power of 3 that divides 6!, exp2 = 2.
   • The largest power of 5 that divides 6!, exp3 = 1.
3. The result is (exp1 + 1) * (exp2 + 1) * (exp3 + 1) … for all prime numbers, For n = 6, the values exp1, exp2, and exp3 are 4 2 and 1 respectively (computed in above step 2). So our result is (4 + 1)*(2 + 1) * (1 + 1) = 30

// allPrimes[] stores all prime numbers less

// than or equal to n.

vector<ull> allPrimes;

 

// Fills above vector allPrimes[] for a given n

void sieve(int n)

{

    // Create a boolean array "prime[0..n]" and

    // initialize all entries it as true. A value

    // in prime[i] will finally be false if i is

    // not a prime, else true.

    vector<bool> prime(n+1, true);

 

    // Loop to update prime[]

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

    {

        // If prime[p] is not changed, then it

        // is a prime

        if (prime[p] == true)

        {

            // Update all multiples of p

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

                prime[i] = false;

        }

    }

 

    // Store primes in the vector allPrimes

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

        if (prime[p])

            allPrimes.push_back(p);

}

 

// Function to find all result of factorial number

ull factorialDivisors(ull n)

{

    sieve(n);  // create sieve

 

    // Initialize result

    ull result = 1;

 

    // find exponents of all primes which divides n

    // and less than n

    for (int i=0; i < allPrimes.size(); i++)

    {

        // Current divisor

        ull p = allPrimes[i];

 

        // Find the highest power (stored in exp)'

        // of allPrimes[i] that divides n using

        // Legendre's formula.

        ull exp = 0;

        while (p <= n)

        {

            exp = exp + (n/p);

            p = p*allPrimes[i];

        }

 

        // Multiply exponents of all primes less

        // than n

        result = result*(exp+1);

    }

 

    // return total divisors

    return result;

}

Read full article from Count Divisors of Factorial - GeeksforGeeks