No of Factors of n!

0 0 8 minutes read

Given a positive integer n, find the no of factors in n! where n <= 10⁵.
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 = p₁^a1 x p₂^a2 x p₃^a3, …., p_k^ak where p₁, p₂, p₃, …., p_k 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:

Iterate from p = 1 to p = n and at each iteration check if p is prime.
If p is prime then it means it is prime factor of n! so we find exponent of p in n! which is
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!:

All prime less than 16 will be the prime factors of 16!. 
so instead of finding all the prime factor of 16!.
we just need to find the primes less than 16 that will 
automatically be the prime 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 <bits/stdc++.h>
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[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;
}
 
// Driver code
int main()
{
    int n = 16;
    printf("Count of factors of %d! is %lld\n",
                                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[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()
    {
        int n = 16;
        Console.Write("Count of factors of " + 
                       n + " is " + countFactors(n));
    }
}
 
// This code is contributed by Nitin Mittal.

PHP

<?php
// PHP program to count 
// number of factors of n
 
// Returns the highest 
// exponent of p in n!
function expFactor($n, $p)
{
    $x = $p;
    $exponent = 0;
    while (intval($n / $x) > 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[1] = 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
?>

Javascript

<script>
// Javascript program to count number of factors of n    
 
    // Sieve of Eratosthenes to mark all prime number
    // in array prime as 1
    function sieve(n, prime)
    {
     
        // Initialize all numbers as prime
        for (let i = 1; i <= n; i++)
            prime[i] = 1;
   
        // Mark composites
        prime[1] = 0;
        for (let i = 2; i * i <= n; i++)
        {
            if (prime[i] == 1) 
            {
                for (let j = i * i; j <= n; j += i)
                    prime[j] = 0;
            }
        }
    }
     
    // Returns the highest exponent of p in n!
    function expFactor(n,p)
    {
        let x = p;
        let exponent = 0;
        while ((n / x) > 0) 
        {
            exponent += Math.floor(n / x);
            x *= p;
        }
        return exponent;
    }
     
    // Returns the no of factors in n!
    function countFactors(n)
    {
     
        // ans stores the no of factors in n!
        let ans = 1;
   
        // Find all primes upto n
        let prime = new Array(n + 1);
        for(let i = 0; i < n + 1; i++)
        {
            prime[i] = 0;
        }
        sieve(n, prime);
   
        // Multiply exponent (of primes) added with 1
        for (let 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
    let n = 16;
    document.write("Count of factors of " + 
                       n + "! is " + countFactors(n));
     
    //  This code is contributed by avanitrachhadiya2155
</script>

Output :

Count of factors of 16! is 5376

Time complexity: O(n log(log n))

Space complexity : O(n)

Note : If the task is to count factors for multiple input values, then we can precompute all prime numbers upto the maximum limit 10⁵.
This article is contributed by Madhur Modi. If you like zambiatek and would like to contribute, you can also write an article using write.zambiatek.com or mail your article to review-team@zambiatek.com. See your article appearing on the zambiatek main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!