Tutorialspoint.dev

Count Divisors of Factorial

Given a number n, count total number of divisors of n!.

Examples:

Input : n = 4
Output: 24
4! is 24. Divisors of 24 are 1, 2, 3, 4, 6,
8, 12 and 24.

Input : n = 5
Output : 16
5! is 120. Divisors of 120 are 1, 2, 3, 4, 
5, 6, 8, 10, 12, 15, 20, 24 30, 40, 60 and 
120

Input : n = 6
Output : 30


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

Below is implementation of above idea.

C++

// C++ program to find count of divisors in n!
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
  
// 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;
}
  
// Driver program to run the cases
int main()
{
    cout << factorialDivisors(6);
    return 0;
}

Java

// JAVA program to find count of divisors in n!
  
import java.util.*;
class GFG
{
    // allPrimes[] stores all prime numbers less
    // than or equal to n.
    static Vector<Integer> allPrimes=new Vector<Integer>();
      
    // Fills above vector allPrimes[] for a given n
    static 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.
        boolean []prime=new boolean[n+1];
          
        for(int i=0;i<=n;i++)
        prime[i]=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.add(p);
        }
          
        // Function to find all result of factorial number
        static long factorialDivisors(int n)
        {
            sieve(n); // create sieve
          
            // Initialize result
            long result = 1;
          
            // find exponents of all primes which divides n
            // and less than n
            for (int i=0; i < allPrimes.size(); i++)
            {
                // Current divisor
                long p = allPrimes.get(i);
          
                // Find the highest power (stored in exp)'
                // of allPrimes[i] that divides n using
                // Legendre's formula.
                long exp = 0;
                while (p <= n)
                {
                    exp = exp + (n/p);
                    p = p*allPrimes.get(i);
                }
          
                // Multiply exponents of all primes less
                // than n
                result = result*(exp+1);
            }
          
            // return total divisors
            return result;
        }
          
        // Driver program to run the cases
        public static void main(String []args)
        {
            System.out.println(factorialDivisors(6));
              
        }
  
  
}
  
//This code is contributed by ihritik

Python3

# Python3 program to find count 
# of divisors in n! 
  
# allPrimes[] stores all prime 
# numbers less than or equal to n. 
allPrimes = []; 
  
# Fills above vector allPrimes[]
# for a given n 
def sieve(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. 
    prime = [True] * (n + 1); 
  
    # Loop to update prime[] 
    p = 2;
    while(p * p <= n):
          
        # If prime[p] is not changed, 
        # then it is a prime 
        if (prime[p] == True):
              
            # Update all multiples of p 
            i = p * 2;
            while(i <= n): 
                prime[i] = False;
                i += p;
        p += 1
  
    # Store primes in the vector allPrimes 
    for p in range(2, n + 1): 
        if (prime[p]): 
            allPrimes.append(p);
  
# Function to find all result of
# factorial number 
def factorialDivisors(n):
  
    sieve(n); # create sieve 
  
    # Initialize result 
    result = 1
  
    # find exponents of all primes 
    # which divides n and less than n 
    for i in range(len(allPrimes)): 
          
        # Current divisor 
        p = allPrimes[i]; 
  
        # Find the highest power (stored in exp)' 
        # of allPrimes[i] that divides n using 
        # Legendre's formula. 
        exp = 0
        while (p <= n):
            exp = exp + int(n / p); 
            p = p * allPrimes[i]; 
  
        # Multiply exponents of all 
        # primes less than n 
        result = result * (exp + 1); 
  
    # return total divisors 
    return result; 
  
# Driver Code
print(factorialDivisors(6)); 
  
# This code is contributed by mits

C#

// C# program to find count of divisors in n!
using System;
using System.Collections;
  
class GFG
{
    // allPrimes[] stores all prime numbers less
    // than or equal to n.
    static ArrayList allPrimes = new ArrayList();
      
    // Fills above vector allPrimes[] for a given n
    static 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.
        bool[] prime = new bool[n+1];
          
        for(int i = 0; i <= n; i++)
        prime[i] = 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.Add(p);
        }
          
        // Function to find all result of factorial number
        static int factorialDivisors(int n)
        {
            sieve(n); // create sieve
          
            // Initialize result
            int result = 1;
          
            // find exponents of all primes which divides n
            // and less than n
            for (int i = 0; i < allPrimes.Count; i++)
            {
                // Current divisor
                int p = (int)allPrimes[i];
          
                // Find the highest power (stored in exp)'
                // of allPrimes[i] that divides n using
                // Legendre's formula.
                int exp = 0;
                while (p <= n)
                {
                    exp = exp + (n / p);
                    p = p * (int)allPrimes[i];
                }
          
                // Multiply exponents of all primes less
                // than n
                result = result * (exp + 1);
            }
          
            // return total divisors
            return result;
        }
          
        // Driver code
        public static void Main()
        {
            Console.WriteLine(factorialDivisors(6));
        }
}
  
//This code is contributed by chandan_jnu

PHP

<?php
// PHP program to find count of 
// divisors in n! 
  
// allPrimes[] stores all prime numbers 
// less than or equal to n. 
$allPrimes = array(); 
  
// Fills above vector allPrimes[] 
// for a given n 
function sieve($n
{
    global $allPrimes;
      
    // 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. 
    $prime = array_fill(0, $n + 1, true); 
  
    // Loop to update prime[] 
    for ($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 ($i = $p * 2; $i <= $n; $i += $p
                $prime[$i] = false; 
        
    
  
    // Store primes in the vector allPrimes 
    for ($p = 2; $p <= $n; $p++) 
        if ($prime[$p]) 
            array_push($allPrimes, $p); 
  
// Function to find all result 
// of factorial number 
function factorialDivisors($n
{
    global $allPrimes;
    sieve($n); // create sieve 
  
    // Initialize result 
    $result = 1; 
  
    // find exponents of all primes 
    // which divides n and less than n 
    for ($i = 0; $i < count($allPrimes); $i++) 
    
        // Current divisor 
        $p = $allPrimes[$i]; 
  
        // Find the highest power (stored in exp)
        // of allPrimes[i] that divides n using 
        // Legendre's formula. 
        $exp = 0; 
        while ($p <= $n
        
            $exp = $exp + (int)($n / $p); 
            $p = $p * $allPrimes[$i]; 
        
  
        // Multiply exponents of all primes 
        // less than n 
        $result = $result * ($exp + 1); 
    
  
    // return total divisors 
    return $result
  
// Driver Code
echo factorialDivisors(6); 
  
// This code is contributed by mits
?>

Output:

30

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter