计算阶乘可以被x整除但不能被y整除的自然数-yiteyi-C++库

给定两个数x和y（x<=y），找出自然数的总数，比如i，其中i！可以被x整除，但不能被y整除。 例如：

null

Input : x = 2, y = 5Output : 3There are three numbers, 2, 3 and 4whose factorials are divisible by xbut not y.Input: x = 15, y = 25Output: 55! = 120 % 15 = 0 && 120 % 25 != 06! = 720 % 15 = 0 && 720 % 25 != 07! = 5040 % 15 = 0 && 5040 % 25 != 08! = 40320 % 15 = 0 && 40320 % 25 != 09! = 362880 % 15 = 0 && 362880 % 25 != 0So total count = 5Input: x = 10, y = 15Output: 0

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

对于所有大于或等于y的数，它们的阶乘都可以被y整除。所以所有要计数的自然数都必须小于y。 A. 简单解决方案 就是从1迭代到y-1，对于每个数字，我检查我！可被x整除，不可被y整除。如果我们采用这种天真的方法，我们不会超过20！或者21岁！（长整型将有其上限） A. 更好的解决方案 基于下面的帖子。找到第一个阶乘可被x整除的自然数我们找到了第一个因子可被x整除的自然数！还有你！使用上述方法。设阶乘可被x和y整除的第一个自然数为 xf 和 yf 分别地我们的最终答案是yf–xf。这个公式基于这样一个事实：如果我！可被数字x整除，然后（i+1）！，（i+2）…也可以被x整除。下面是实现。

C++

                         // C++ program to count natural numbers whose                       
                         // factorials are divisible by x but not y.                       
                         #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                       
                         // is divisible by 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;                       
                         }                       
           
                         // Count of natural numbers whose factorials                       
                         // are divisible by x but not y.                       
                         int                                     countFactorialXNotY(                                     int                                     x,                                     int                                     y)                       
                         {                       
                                                 // Return difference between first natural                       
                                                 // number whose factorial is divisible by                       
                                                 // y and first natural number whose factorial                       
                                                 // is divisible by x.                       
                                                 return                                     (firstFactorialDivisibleNumber(y) -                       
                                                 firstFactorialDivisibleNumber(x));                       
                         }                       
           
                         // Driver code                       
                         int                                     main(                                     void                                     )                       
                         {                       
                                                 int                                     x = 15, y = 25;                       
                                                 cout << countFactorialXNotY(x, y);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to count natural numbers whose                       
                         // factorials are divisible by x but not y.                       
           
                         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                       
                                                 // is divisible by 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;                       
                                                 }                       
                                   
                                                 // Count of natural numbers whose factorials                       
                                                 // are divisible by x but not y.                       
                                                 static                                     int                                     countFactorialXNotY(                                     int                                     x,                                     int                                     y)                       
                                                 {                       
                                                 // Return difference between first natural                       
                                                 // number whose factorial is divisible by                       
                                                 // y and first natural number whose factorial                       
                                                 // is divisible by x.                       
                                                 return                                     (firstFactorialDivisibleNumber(y) -                       
                                                 firstFactorialDivisibleNumber(x));                       
                                                 }                       
                                   
                                                 // Driver code                       
                                                 public                                     static                                     void                                     main (String[] args)                       
                                                 {                       
                                                 int                                     x =                                     15                                     , y =                                     25                                     ;                       
                                                 System.out.print(countFactorialXNotY(x, y));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Anant Agarwal.                       

Python3

                         # Python program to count natural                       
                         # numbers whose factorials are                       
                         # divisible by x but not y.                       
           
                         # 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                       
                         # is divisible by x.                       
                         def                                     firstFactorialDivisibleNumber(x):                       
                                   
                                                 # Result                       
                                                 i                                     =                                     1                       
                                                 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                       
           
                         # Count of natural numbers whose                       
                         # factorials are divisible by x but                       
                         # not y.                       
                         def                                     countFactorialXNotY(x, y):                       
           
                                                 # Return difference between first                       
                                                 # natural number whose factorial                       
                                                 # is divisible by y and first                       
                                                 # natural number whose factorial                       
                                                 # is divisible by x.                       
                                                 return                                     (firstFactorialDivisibleNumber(y)                                     -                       
                                                 firstFactorialDivisibleNumber(x))                       
                                   
                         # Driver code                       
                         x                                     =                                     15                       
                         y                                     =                                     25                       
           
                         print                                     (countFactorialXNotY(x, y))                       
           
                         # This code is contributed by Anant Agarwal.                       

C#

                         // C# program to count natural numbers whose                       
                         // factorials are divisible by x but not y.                       
                         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                       
                                                 // is divisible by 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;                       
                                                 }                       
                                   
                                                 // Count of natural numbers whose factorials                       
                                                 // are divisible by x but not y.                       
                                                 static                                     int                                     countFactorialXNotY(                                     int                                     x,                                     int                                     y)                       
                                                 {                       
                                   
                                                 // Return difference between first natural                       
                                                 // number whose factorial is divisible by                       
                                                 // y and first natural number whose factorial                       
                                                 // is divisible by x.                       
                                                 return                                     (firstFactorialDivisibleNumber(y) -                       
                                                 firstFactorialDivisibleNumber(x));                       
                                                 }                       
                                   
                                                 // Driver code                       
                                                 public                                     static                                     void                                     Main ()                       
                                                 {                       
                                                 int                                     x = 15, y = 25;                       
                                   
                                                 Console.Write(countFactorialXNotY(x, y));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by nitin mittal.                       

PHP

                         <?php                       
                         // PHP program to count natural                       
                         // numbers whose factorials are                       
                         // divisible by x but not y.                       
           
                         // 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 is divisible by 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                                     ;                       
                         }                       
           
                         // Count of natural numbers                       
                         // whose factorials are divisible                       
                         // by x but not y.                       
                         function                                     countFactorialXNotY(                                     $x                                     ,                                     $y                                     )                       
                         {                       
                                                 // Return difference between                       
                                                 // first natural number whose                       
                                                 // factorial is divisible by                       
                                                 // y and first natural number                       
                                                 // whose factorial is divisible by x.                       
                                                 return                                     (firstFactorialDivisibleNumber(                                     $y                                     ) -                       
                                                 firstFactorialDivisibleNumber(                                     $x                                     ));                       
                         }                       
           
                         // Driver code                       
                         $x                                     = 15;                                     $y                                     = 25;                       
                         echo                                     (countFactorialXNotY(                                     $x                                     ,                                     $y                                     ));                       
           
                         // This code is contributed by Ajit.                       
                         ?>                       

Javascript

                         <script>                       
           
                         // Javascript program to Merge two sorted halves of                       
                         // array Into Single Sorted Array                       
           
                                                 // 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                       
                                                 // is divisible by x.                       
                                                 function                                     firstFactorialDivisibleNumber(x)                       
                                                 {                       
                                                 let i = 1;                                     // Result                       
                                                 let 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;                       
                                                 }                       
                                   
                                                 // Count of natural numbers whose factorials                       
                                                 // are divisible by x but not y.                       
                                                 function                                     countFactorialXNotY(x, y)                       
                                                 {                       
                                                 // Return difference between first natural                       
                                                 // number whose factorial is divisible by                       
                                                 // y and first natural number whose factorial                       
                                                 // is divisible by x.                       
                                                 return                                     (firstFactorialDivisibleNumber(y) -                       
                                                 firstFactorialDivisibleNumber(x));                       
                                                 }                       
                                   
                                   
                         // Driver code                       
           
                                                 let x = 15, y = 25;                       
                                                 document.write(countFactorialXNotY(x, y));                       
                                   
                         </script>                       

输出：

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

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

THE END

技术文章