## Friday, September 16, 2016

### 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;`
`}`