Tutorialspoint.dev

Find the first natural number whose factorial is divisible by x

Given a number x, the task is to find first natural number i whose factorial is divisible by x.

Examples :

Input  : x = 10
Output : 5
5 is the smallest number such that 
(5!) % 10 = 0

Input  : x = 16
Output : 6
6 is the smallest number such that 
(6!) % 16 = 0



A simple solution is to iterate from 1 to x-1 and for every number i check if i! is divisible by x.

C++

// A simple C++ program to find first natural
// number whose factorial divides x.
#include <bits/stdc++.h>
using namespace std;
  
// Returns first number whose factorial
// divides x.
int firstFactorialDivisibleNumber(int x)
{
    int i = 1; // Result
    int fact = 1;
    for (i = 1; i < x; i++) {
        fact = fact * i;
        if (fact % x == 0)
            break;
    }
  
    return i;
}
  
// Driver code
int main(void)
{
    int x = 16;
    cout << firstFactorialDivisibleNumber(x);
    return 0;
}

Java

// A simple Java program to find first natural
// number whose factorial divides x
class GFG {
  
    // Returns first number whose factorial
    // divides x.
    static int firstFactorialDivisibleNumber(int x)
    {
        int i = 1; // Result
        int fact = 1;
        for (i = 1; i < x; i++) {
            fact = fact * i;
            if (fact % x == 0)
                break;
        }
  
        return i;
    }
  
    // Driver code
    public static void main(String[] args)
    {
        int x = 16;
        System.out.print(firstFactorialDivisibleNumber(x));
    }
}
  
// This code is contributed by Anant Agarwal.

Python3

# A simple python program to find 
# first natural number whose 
# factorial divides x.
  
# Returns first number whose 
# factorial divides x.
def firstFactorialDivisibleNumber(x):
    i = 1; # Result
    fact = 1;
    for i in range(1, x):
        fact = fact * i
        if (fact % x == 0):
            break
    return i
  
# Driver code
x = 16
print(firstFactorialDivisibleNumber(x))
  
# This code is contributed 
# by 29AjayKumar

C#

// A simple C# program to find first natural
// number whose factorial divides x
using System;
  
class GFG {
  
    // Returns first number whose factorial
    // divides x.
    static int firstFactorialDivisibleNumber(int x)
    {
        int i = 1; // Result
        int fact = 1;
        for (i = 1; i < x; i++) {
            fact = fact * i;
            if (fact % x == 0)
                break;
        }
  
        return i;
    }
  
    // Driver code
    public static void Main()
    {
        int x = 16;
  
        Console.Write(
            firstFactorialDivisibleNumber(x));
    }
}
  
// This code is contributed by nitin mittal

PHP

<?php
// A simple PHP program to find
// first natural number whose 
// factorial divides x.
  
// Returns first number whose
// factorial divides x.
function firstFactorialDivisibleNumber($x)
{
    // Result
    $i = 1; 
    $fact = 1;
    for ($i = 1; $i < $x; $i++) 
    {
        $fact = $fact * $i;
        if ($fact % $x == 0)
            break;
    }
  
    return $i;
}
  
// Driver code
$x = 16;
echo(firstFactorialDivisibleNumber($x));
  
// This code is contributed by Ajit.
?>


Output :

6

If we apply this naive approach, we wouldn’t go above 20! or 21! (long long int will have its upper limit).

A better solution avoids overflow. The solution is based on below observations.

  • If i! is divisible by x, then (i+1)!, (i+2)!, … are also divisible by x.
  • For a number x, all factorials i! are divisible by x when i >= x.
  • If a number x is prime, then no factorial below x can divide it as x cannot be formed with multiplication of smaller numbers.

Below is algorithm

1) Run a loop for i = 1 to n-1
       
   a) Remove common factors
      new_x /= gcd(i, new_x);

   b) Check if we found first i.
      if (new_x == 1)
          break;

2) Return i

Below is the implementation of above idea :

CPP

// C++ program to find first natural number
// whose factorial divides x.
#include <bits/stdc++.h>
using namespace std;
  
// GCD function to compute the greatest
// divisor among a and b
int gcd(int a, int b)
{
    if ((a % b) == 0)
        return b;
    return gcd(b, a % b);
}
  
// Returns first number whose factorial
// divides x.
int firstFactorialDivisibleNumber(int x)
{
    int i = 1; // Result
    int new_x = x;
  
    for (i = 1; i < x; i++) {
        // Remove common factors
        new_x /= gcd(i, new_x);
  
        // We found first i.
        if (new_x == 1)
            break;
    }
    return i;
}
  
// Driver code
int main(void)
{
    int x = 16;
    cout << firstFactorialDivisibleNumber(x);
    return 0;
}

Java

// Efficient Java program to find first
// natural number whose factorial divides x.
class GFG {
  
    // GCD function to compute the greatest
    // divisor among a and b
    static int gcd(int a, int b)
    {
        if ((a % b) == 0)
            return b;
        return gcd(b, a % b);
    }
  
    // Returns first number whose factorial
    // divides x.
    static int firstFactorialDivisibleNumber(int x)
    {
        int i = 1; // Result
        int new_x = x;
  
        for (i = 1; i < x; i++) {
  
            // Remove common factors
            new_x /= gcd(i, new_x);
  
            // We found first i.
            if (new_x == 1)
                break;
        }
        return i;
    }
  
    // Driver code
    public static void main(String[] args)
    {
        int x = 16;
        System.out.print(firstFactorialDivisibleNumber(x));
    }
}
// This code is contributed by Anant Agarwal.

Python3

      
#  Python3 program to find first natural number
#  whose factorial divides x.
  
   
#  GCD function to compute the greatest
#  divisor among a and b
def gcd(a,  b):
    if ((a % b) == 0):
        return b
    return gcd(b, a % b)
  
   
#  Returns first number whose factorial
#  divides x.
def firstFactorialDivisibleNumber(x):
    i = 1 #  Result
    new_x = x
   
    for i in range(1,x):
        #  Remove common factors
        new_x /= gcd(i, new_x)
   
        #  We found first i.
        if (new_x == 1):
            break
    return i
   
#  Driver code
def main():
    x = 16
    print(firstFactorialDivisibleNumber(x))
  
if __name__ == '__main__':
    main()
  
# This code is contributed by 29AjayKumar 

C#

// Efficient C# program to find first
// natural number whose factorial 
// divides x.
using System;
  
class GFG {
  
    // GCD function to compute the
    // greatest divisor among a
    // and b
    static int gcd(int a, int b)
    {
        if ((a % b) == 0)
            return b;
        return gcd(b, a % b);
    }
  
    // Returns first number whose
    // factorial divides x.
    static int firstFactorialDivisibleNumber(
                                        int x)
    {
        int i = 1; // Result
        int new_x = x;
  
        for (i = 1; i < x; i++) {
  
            // Remove common factors
            new_x /= gcd(i, new_x);
  
            // We found first i.
            if (new_x == 1)
                break;
        }
          
        return i;
    }
  
    // Driver code
    public static void Main()
    {
        int x = 16;
        Console.Write(
            firstFactorialDivisibleNumber(x));
    }
}
  
// This code is contributed by nitin mittal.

PHP

<?php
// PHP program to find first 
// natural number whose 
// factorial divides x.
  
// GCD function to compute the 
// greatest divisor among a and b
function gcd($a, $b)
{
    if (($a % $b) == 0)
        return $b;
    return gcd($b, $a % $b);
}
  
// Returns first number 
// whose factorial divides x.
function firstFactorialDivisibleNumber($x)
{
    // Result
    $i = 1; 
    $new_x = $x;
  
    for ($i = 1; $i < $x; $i++) 
    {
        // Remove common factors
        $new_x /= gcd($i, $new_x);
  
        // We found first i.
        if ($new_x == 1)
            break;
    }
    return $i;
}
  
// Driver code
$x = 16;
echo(firstFactorialDivisibleNumber($x));
  
// This code is contributed by Ajit.
?>

Output :

6



Another approach using boost library:
(Thanking ajay0007 for contributing this approach)
Here we use boost library to efficiently calculate the value of factorial.
Prerequisite :boost-multiprecision-library

C++

// A cpp program for finding 
// the Special Factorial Number
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
  
using boost::multiprecision::cpp_int;
using namespace std;
  
// function for calculating factoial
cpp_int fact(int n)
{
    cpp_int num = 1;
      
    for (int i = 1; i <= n; i++)
        num = num * i;
      
    return num;
}
  
// function for check Special_Factorial_Number
int Special_Factorial_Number(int k)
{
      
    for(int i = 1 ; i <= k ; i++ )
    
        // call fact function and the 
        // Modulo with k and check
        // if condition is TRUE then return i
        if ( ( fact (i) % k ) == 0 )
        {
            return i;
        }
    }
}
  
//driver function
int main()
{
    // taking input
    int k = 16;
      
    cout<<Special_Factorial_Number(k);
}

Java

// Java program for finding 
// the Special Factorial Number 
public class GFG {
  
// function for calculating factoial 
    static int fact(int n) {
        int num = 1;
  
        for (int i = 1; i <= n; i++) {
            num = num * i;
        }
  
        return num;
    }
  
// function for check Special_Factorial_Number 
    static int Special_Factorial_Number(int k) {
  
        for (int i = 1; i <= k; i++) {
            // call fact function and the 
            // Modulo with k and check 
            // if condition is TRUE then return i 
            if (fact(i) % k == 0) {
                return i;
            }
        }
        return 0;
    }
  
//driver function 
    public static void main(String[] args) {
        // taking input 
        int k = 16;
        System.out.println(Special_Factorial_Number(k));
  
    }
}
  
/*This code is contributed by Rajput-Ji*/

Python3

# Python 3 program for finding
# the Special Factorial Number

# function for calculating factoial
def fact( n):
num = 1
for i in range(1, n + 1):
num = num * i
return num

# function for check Special_Factorial_Number
def Special_Factorial_Number(k):

for i in range(1, k + 1):

# call fact function and the
# Modulo with k and check
# if condition is TRUE then return i
if (fact(i) % k == 0):
return i
return 0

# Driver Code
if __name__ == ‘__main__’:

# taking input
k = 16
print(Special_Factorial_Number(k))

# This code is contributed by Rajput-Ji

C#

// C# program for finding 
// the Special Factorial Number 
using System; 
public class GFG{
  
  
// function for calculating factoial 
    static int fact(int n) { 
        int num = 1; 
  
        for (int i = 1; i <= n; i++) { 
            num = num * i; 
        
  
        return num; 
    
  
// function for check Special_Factorial_Number 
    static int Special_Factorial_Number(int k) { 
  
        for (int i = 1; i <= k; i++) { 
            // call fact function and the 
            // Modulo with k and check 
            // if condition is TRUE then return i 
            if (fact(i) % k == 0) { 
                return i; 
            
        
        return 0; 
    
  
//driver function 
    public static void Main() { 
        // taking input 
        int k = 16; 
        Console.WriteLine(Special_Factorial_Number(k)); 
  
    
  
// This code is contributed by 29AjayKumar

PHP

<?php
// PHP program for finding 
// the Special Factorial Number
  
// function for calculating 
// factoial
function fact($n)
{
    $num = 1;
      
    for ($i = 1; $i <= $n; $i++)
        $num = $num * $i;
      
    return $num;
}
  
// function for check 
// Special_Factorial_Number
function Special_Factorial_Number($k)
{
      
    for($i = 1 ; $i <= $k ; $i++ )
    
          
        // call fact function and the 
        // Modulo with k and check
        // if condition is TRUE 
        // then return i
        if (( fact ($i) % $k ) == 0 )
        {
            return $i;
        }
    }
}
  
    // Driver Code
    $k = 16;
    echo Special_Factorial_Number($k);
  
// This code is contributed by Ajit.
?>


Output :

6

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