找到第一个阶乘可被x整除的自然数-yiteyi-C++库

给定一个数x，任务是找到第一个自然数i，其阶乘可被x整除。 例如：

null

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

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

A. 简单解决方案 就是从1迭代到x-1，对于每一个数字，我检查！可被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>                       

输出：

如果我们采用这种天真的方法，我们不会超过20！或者21岁！（long int将有其上限）。 A. 更好的解决方案 避免溢出。解决方案基于以下观察结果。

如果我！可被x整除，然后（i+1）！，（i+2）…也可以被x整除。
对于一个数字x，所有的阶乘i！当i>=x时可被x整除。
如果一个数x是素数，那么x以下的阶乘就不能将其除，因为x不能由较小的数相乘而形成。

下面是算法

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

以下是上述理念的实施：

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>                       

输出：

另一种方法 使用boost库： （感谢ajay0007对这种方法的贡献） 这里我们使用boost库来高效地计算阶乘的值。先决条件： boost多精度库

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>                       

输出：

本文由 舒巴姆·古普塔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章