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. ?> |
Javascript
<script> // A simple Javascript program to find first natural // number whose factorial divides x. // Returns first number whose factorial // divides x. function firstFactorialDivisibleNumber(x) { var i = 1; // Result var fact = 1; for (i = 1; i < x; i++) { fact = fact * i; if (fact % x == 0) break ; } return i; } // Driver code var x = 16; document.write(firstFactorialDivisibleNumber(x)); // This code is contributed by noob2000. </script> |
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 the above idea :
C++
// 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. ?> |
Javascript
<script> // Efficient Javascript 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) { let i = 1; // Result let new_x = x; for (i = 1; i < x; i++) { // Remove common factors new_x = parseInt(new_x / gcd(i, new_x), 10); // We found first i. if (new_x == 1) break ; } return i; } let x = 16; document.write(firstFactorialDivisibleNumber(x)); // This code is contributed by divyeshrabadiya07. </script> |
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 factorial 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 factorial 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 factorial 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 factorial 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 // factorial 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. ?> |
Javascript
<script> // Javascript program for finding the Special Factorial Number // function for calculating factorial function fact(n) { let num = 1; for (let i = 1; i <= n; i++) { num = num * i; } return num; } // function for check Special_Factorial_Number function Special_Factorial_Number(k) { for (let 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; } // taking input let k = 16; document.write(Special_Factorial_Number(k)); </script> |
Output :
6
Time complexity: O(n^2) since using a for loop in another for loop
Auxiliary Space: O(1) because it is using constant variable
Method 4: Using a generator
This code uses generators and loops to find the first natural number whose factorial is divisible by a given number x.
The factorial_gen() function is a generator that yields the factorial of each natural number starting from 1. It uses a while loop that keeps multiplying the current factorial with the next natural number and yields the result at each iteration.
The factorial_divisible_by_x() function takes the input x and loops through the factorials generated by factorial_gen(). It checks if the current factorial is divisible by x using the modulo operator. If it is, then the function returns the index of the natural number (i+1) whose factorial was found to be divisible by x.
Finally, the code calls the factorial_divisible_by_x() function with x = 10 and prints the result.
C++
#include <iostream> using namespace std; int main() { int fact = 1; int i = 1; int x = 10; int count = 0; while ( true ) { if (fact % x == 0) { count = i; break ; } i++; fact *= i; } cout << count << endl; return 0; } |
Java
public class Main { public static void main(String[] args) { int fact = 1 ; // initialize factorial to 1 int i = 1 ; // initialize counter to 1 int x = 10 ; // set the value of x int count = 0 ; // initialize count to 0 while ( true ) { // loop until a break statement is // executed if (fact % x == 0 ) { // check if the factorial // is divisible by x count = i; // set the count to the current // value of i break ; // exit the loop } i++; // increment the counter fact *= i; // calculate the factorial } System.out.println(count); // print the count } } |
Python3
def factorial_gen(): fact = 1 i = 1 while True : yield fact i + = 1 fact * = i def factorial_divisible_by_x(x): for i, f in enumerate (factorial_gen()): if f % x = = 0 : return i + 1 x = 10 print (factorial_divisible_by_x(x)) |
Javascript
// Example usage let x = 10; let fact = 1; let i = 1; let count = 0; while ( true ) { if (fact % x === 0) { count = i; break ; } i++; fact *= i; } console.log(count); |
C#
using System; class Program { static void Main( string [] args) { int fact = 1; int i = 1; int x = 10; int count = 0; while ( true ) { if (fact % x == 0) { count = i; break ; } i++; fact *= i; } Console.WriteLine(count); } } |
5
The time complexity of the factorial_divisible_by_x function depends on the value of x and the number of iterations it takes to find the first factorial that is divisible by x. The factorial_gen generator function has a time complexity of O(n) as it generates factorials endlessly.
The space complexity of both functions is O(1) as they only use a fixed number of variables to store the factorial and the index. The factorial_gen generator does not store all the factorials it generates at once, but only the latest one.
Contact Us