# No of Factors of n!

Given a positive integer n, find the no of factors in n! where n <= 105.

Examples :

```Input : n = 3
Output : 4
Factors of 3! are 1, 2, 3, 6

Input : n = 4
Output : 8
Factors of 4! are 1, 2, 3, 4,
6, 8, 12, 24

Input : n = 16
Output : 5376
```

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.

The idea is based on Legendre’s formula.

Any positive integer can be expressed as product of power of its prime factors. Suppose a number n = p1a1 x p2a2 x 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:

br>
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)
```Here is an illustration on how the algorithm works
for finding factors of 16!:

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
= 15

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) * (3+1) *(2+1)* (1+1) * (1+1)
= 5376 ```

Below is the implementation of above idea:

## C++

 `// C++ program to count number of factors of n ` `#include ` `using` `namespace` `std; ` `typedef` `long` `long` `int` `ll; ` ` `  `// Sieve of Eratosthenes to mark all prime number ` `// in array prime as 1 ` `void` `sieve(``int` `n, ``bool` `prime[]) ` `{ ` `    ``// Initialize all numbers as prime ` `    ``for` `(``int` `i=1; i<=n; i++) ` `        ``prime[i] = 1; ` ` `  `    ``// Mark composites ` `    ``prime = 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; ` `} ` ` `  `// Driver code ` `int` `main() ` `{ ` `    ``int` `n = 16; ` `    ``printf``(````"Count of factors of %d! is %lld "````, ` `                                ``n, countFactors(n)); ` `    ``return` `0; ` `} `

## Java

 `// Java program to count number of factors of n ` `import` `java.io.*; ` `class` `GFG { ` ` `  `    ``// Sieve of Eratosthenes to mark all prime number ` `    ``// in array prime as 1 ` `    ``static` `void` `sieve(``int` `n, ``int` `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] == ``1``) { ` `                ``for` `(``int` `j = i * i; j <= n; j += i) ` `                    ``prime[j] = ``0``; ` `            ``} ` `        ``} ` `    ``} ` ` `  `    ``// Returns the highest exponent of p in n! ` `    ``static` `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! ` `    ``static` `long` `countFactors(``int` `n) ` `    ``{ ` `        ``// ans stores the no of factors in n! ` `        ``long` `ans = ``1``; ` ` `  `        ``// Find all primes upto n ` `        ``int` `prime[] = ``new` `int``[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; ` `    ``} ` ` `  `    ``// Driver code ` `     ``public` `static` `void` `main(String args[]) ` `    ``{ ` `        ``int` `n = ``16``; ` `        ``System.out.println(``"Count of factors of "` `+  ` `                       ``n + ``" is "` `+ countFactors(n)); ` `    ``} ` `} ` `// This code is contributed by Nikita Tiwari `

## Python 3

 `# python 3 program to count  ` `# number of factors of n ` ` `  `# Returns the highest  ` `# exponent of p in n! ` `def` `expFactor(n, p): ` `    ``x ``=` `p ` `    ``exponent ``=` `0` `    ``while` `n ``/``/` `x > ``0``: ` `     `  `        ``exponent ``+``=` `n ``/``/` `x ` `        ``x ``*``=` `p ` `    ``return` `exponent ` ` `  `# Returns the no  ` `# of factors in n! ` `def` `countFactors(n): ` ` `  `    ``# ans stores the no ` `    ``# of factors in n! ` `    ``ans ``=` `1` ` `  `    ``# Find all primes upto n ` `    ``prime ``=` `[``None``]``*``(n``+``1``) ` `     `  `    ``# Initialize all ` `    ``# numbers as prime ` `    ``for` `i ``in` `range``(``1``,n``+``1``): ` `        ``prime[i] ``=` `1` ` `  `    ``# Mark composites ` `    ``prime[``1``] ``=` `0` `    ``i ``=` `2` `    ``while` `i ``*` `i <``=` `n: ` `     `  `        ``if` `(prime[i]): ` `         `  `            ``for` `j ``in` `range``(i ``*` `i,n``+``1``,i): ` `                ``prime[j] ``=` `0` `        ``i ``+``=` `1` ` `  `    ``# Multiply exponent (of ` `    ``# primes) added with 1 ` `    ``for` `p ``in` `range``(``1``,n``+``1``): ` `     `  `        ``# 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 ` ` `  `# Driver Code ` `if` `__name__``=``=``'__main__'``: ` `    ``n ``=` `16` `    ``print``(``"Count of factors of "` `+` `str``(n) ``+` `         ``"! is "` `+``str``( countFactors(n))) ` `          `  `# This code is contributed by ChitraNayal `

## C#

 `// C# program to count number  ` `// of factors of n ` `using` `System; ` ` `  `class` `GFG { ` ` `  `    ``// Sieve of Eratosthenes to mark all  ` `    ``// prime number in array prime as 1 ` `    ``static` `void` `sieve(``int` `n, ``int` `[]prime) ` `    ``{ ` `         `  `        ``// Initialize all numbers as prime ` `        ``for` `(``int` `i = 1; i <= n; i++) ` `            ``prime[i] = 1; ` ` `  `        ``// Mark composites ` `        ``prime = 0; ` `        ``for` `(``int` `i = 2; i * i <= n; i++) ` `        ``{ ` `            ``if` `(prime[i] == 1)  ` `            ``{ ` `                ``for` `(``int` `j = i * i; j <= n; j += i) ` `                    ``prime[j] = 0; ` `            ``} ` `        ``} ` `    ``} ` ` `  `    ``// Returns the highest exponent of p in n! ` `    ``static` `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! ` `    ``static` `long` `countFactors(``int` `n) ` `    ``{ ` `        ``// ans stores the no of factors in n! ` `        ``long` `ans = 1; ` ` `  `        ``// Find all primes upto n ` `        ``int` `[]prime = ``new` `int``[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; ` `    ``} ` ` `  `    ``// Driver code ` `    ``public` `static` `void` `Main() ` `    ``{ ` `        ``int` `n = 16; ` `        ``Console.Write(``"Count of factors of "` `+  ` `                       ``n + ``" is "` `+ countFactors(n)); ` `    ``} ` `} ` ` `  `// This code is contributed by Nitin Mittal. `

## PHP

 ` 0) ` `    ``{ ` `        ``\$exponent` `+= ``intval``(``\$n` `/ ``\$x``); ` `        ``\$x` `*= ``\$p``; ` `    ``} ` `    ``return` `\$exponent``; ` `} ` ` `  `// Returns the no  ` `// of factors in n! ` `function` `countFactors(``\$n``) ` `{ ` `    ``// ans stores the no ` `    ``// of factors in n! ` `    ``\$ans` `= 1; ` ` `  `    ``// Find all primes upto n ` `    ``\$prime` `= ``array``(); ` `     `  `    ``// Initialize all ` `    ``// numbers as prime ` `    ``for` `(``\$i` `= 1; ``\$i` `<= ``\$n``; ``\$i``++) ` `        ``\$prime``[``\$i``] = 1; ` ` `  `    ``// Mark composites ` `    ``\$prime`` = 0; ` `    ``for` `(``\$i` `= 2; ``\$i` `* ``\$i` `<= ``\$n``; ``\$i``++) ` `    ``{ ` `        ``if` `(``\$prime``[``\$i``]) ` `        ``{ ` `            ``for` `(``\$j` `= ``\$i` `* ``\$i``; ``\$j` `<= ``\$n``; ``\$j` `+= ``\$i``) ` `                ``\$prime``[``\$j``] = 0; ` `        ``} ` `    ``} ` ` `  `    ``// Multiply exponent (of ` `    ``// primes) added with 1 ` `    ``for` `(``\$p` `= 1; ``\$p` `<= ``\$n``; ``\$p``++) ` `    ``{ ` `        ``// if p is a prime then p  ` `        ``// is also a prime factor of n! ` `        ``if` `(``\$prime``[``\$p``] == 1) ` `            ``\$ans` `*= ``intval``(expFactor(``\$n``, ``\$p``) + 1); ` `    ``} ` ` `  `    ``return` `\$ans``; ` `} ` ` `  `// Driver Code ` `\$n` `= 16; ` `echo` `"Count of factors of "` `. ``\$n` `.  ` `       ``"! is "` `. countFactors(``\$n``); ` `     `  `// This code is contributed by Sam007 ` `?> `

Output :

`Count of factors of 16! is 5376 `

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