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 codeint main(void){ int x = 16; cout << firstFactorialDivisibleNumber(x); return 0;} |
Java
// A simple Java program to find first natural// number whose factorial divides xclass 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 codex = 16print(firstFactorialDivisibleNumber(x))# This code is contributed # by 29AjayKumar |
C#
// A simple C# program to find first natural// number whose factorial divides xusing 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> |
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 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 bdef 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 codedef 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 bfunction 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> |
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 factorialcpp_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_Numberint 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 functionint 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 Codeif __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 // factorialfunction fact($n){ $num = 1; for ($i = 1; $i <= $n; $i++) $num = $num * $i; return $num;}// function for check // Special_Factorial_Numberfunction 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 *= idef factorial_divisible_by_x(x): for i, f in enumerate(factorial_gen()): if f % x == 0: return i+1x = 10print(factorial_divisible_by_x(x)) |
Javascript
// Example usagelet 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); }} |
Output
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.
This article is contributed by Shubham Gupta. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen 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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
