## Friday, June 24, 2016

### 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 <= 105.

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.