n中质数r的幂！-yiteyi-C++库

给定一个整数n，求给定素数（r）在n中的幂！ 例如：

null

Input  : n = 6  r = 3         Factorial of 6 is 720 = 2^4 * 3^2 *5 (prime factor 2,3,5)         and power of 3 is 2 Output : 2Input  : n = 2000 r = 7Output : 330

一个简单的方法是先计算n的阶乘，然后对它进行阶乘运算，求出素数的幂。上述方法可能会导致稍大的数字溢出，因为数字的阶乘是一个大数字。其思想是考虑阶乘n的素因子。 n的勒让德分解！ 对于任意素数p和任意整数n，让 副总裁（n） 是p除以n的最大幂的指数（即n的p-adic估值）。然后 Vp（n）=楼层（n/p^i）和i的总和从1到无穷大虽然右边的公式是一个无限和，但对于n和p的任何特定值，它只有有限多个非零项：对于每一个足够大到p^i>n的i，一个有下限（n/p^i）=0。因为，和是收敛的。

Power of ‘r’ in n! = floor(n/r) + floor(n/r^2) + floor(n/r^3) + ....

计算n中r的幂的程序！基于上述公式。

C++

                         // C++ program to find power of                       
                         // a prime number ‘r’ in n!                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Function to return power of a                       
                         // no. 'r' in factorial of n                       
                         int                                     power(                                     int                                     n,                                     int                                     r)                       
                         {                       
                                                 // Keep dividing n by powers of                       
                                                 // 'r' and update count                       
                                                 int                                     count = 0;                       
                                                 for                                     (                                     int                                     i = r; (n / i) >= 1; i = i * r)                       
                                                 count += n / i;                       
                                                 return                                     count;                       
                         }                       
           
                         // Driver program to                       
                         // test above function                       
                         int                                     main()                       
                         {                       
                                                 int                                     n = 6,  r = 3;                       
                                                 printf                                     (                                     " %d "                                     , power(n, r));                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to find power of                       
                         // a prime number 'r' in n!                       
           
                         class                                     GFG {                       
                                   
                         // Function to return power of a                       
                         // no. 'r' in factorial of n                       
                         static                                     int                                     power(                                     int                                     n,                                     int                                     r) {                       
                                   
                                                 // Keep dividing n by powers of                       
                                                 // 'r' and update count                       
                                                 int                                     count =                                     0                                     ;                       
                                                 for                                     (                                     int                                     i = r; (n / i) >=                                     1                                     ; i = i * r)                       
                                                 count += n / i;                       
                                                 return                                     count;                       
                         }                       
           
                         // Driver code                       
                         public                                     static                                     void                                     main(String[] args)                       
                         {                       
                                                 int                                     n =                                     6                                     , r =                                     3                                     ;                       
                                                 System.out.print(power(n, r));                       
                         }                       
                         }                       
           
                         // This code is contributed by Anant Agarwal.                       

Python3

                         # Python3 program to find power                       
                         # of a prime number ‘r’ in n!                       
           
                         # Function to return power of a                       
                         # no. 'r' in factorial of n                       
                         def                                     power(n, r):                       
                                   
                                                 # Keep dividing n by powers of                       
                                                 # 'r' and update count                       
                                                 count                                     =                                     0                                     ; i                                     =                                     r                       
                                   
                                                 while                                     ((n                                     /                                     i) >                                     =                                     1                                     ):                       
                                                 count                                     +                                     =                                     n                                     /                                     i                       
                                                 i                                     =                                     i                                     *                                     r                       
                                   
                                                 return                                     int                                     (count)                       
           
                         # Driver Code                       
                         n                                     =                                     6                                     ; r                                     =                                     3                       
                         print                                     (power(n, r))                       
           
                         # This code is contributed by Smitha Dinesh Semwal.                       

C#

                         // C# program to find power of                       
                         // a prime number 'r' in n!                       
                         using                                     System;                       
           
                         class                                     GFG {                       
                                   
                         // Function to return power of a                       
                         // no. 'r' in factorial of n                       
                         static                                     int                                     power(                                     int                                     n,                                     int                                     r) {                       
                                   
                                                 // Keep dividing n by powers of                       
                                                 // 'r' and update count                       
                                                 int                                     count = 0;                       
                                                 for                                     (                                     int                                     i = r; (n / i) >= 1; i = i * r)                       
                                                 count += n / i;                       
                                                 return                                     count;                       
                         }                       
           
                         // Driver code                       
                         public                                     static                                     void                                     Main()                       
                         {                       
                                                 int                                     n = 6, r = 3;                       
                                                 Console.WriteLine(power(n, r));                       
                         }                       
                         }                       
           
                         // This code is contributed by vt_m.                       

PHP

                         <?php                       
                         //PHP program to find power of                       
                         // a prime number ‘r’ in n!                       
           
                         // Function to return power of a                       
                         // no. 'r' in factorial of n                       
                         function                                     power(                                     $n                                     ,                                     $r                                     )                       
                         {                       
                                   
                                                 // Keep dividing n by powers                       
                                                 // of 'r' and update count                       
                                                 $count                                     = 0;                       
                                                 for                                     (                                     $i                                     =                                     $r                                     ; (                                     $n                                     /                                     $i                                     ) >= 1;                       
                                                 $i                                     =                                     $i                                     *                                     $r                                     )                       
                                                 $count                                     +=                                     $n                                     /                                     $i                                     ;                       
                                                 return                                     $count                                     ;                       
                         }                       
           
                                                 // Driver Code                       
                                                 $n                                     = 6;                                     $r                                     = 3;                       
                                                 echo                                     power(                                     $n                                     ,                                     $r                                     );                       
           
                         // This code is contributed by ajit                       
                         ?>                       

Javascript

                         <script>                       
           
                         // JavaScript program to find power of                       
                         // a prime number 'r' in n!                       
           
                         // Function to return power of a                       
                         // no. 'r' in factorial of n                       
                         function                                     power(n, r) {                       
                                   
                                                 // Keep dividing n by powers of                       
                                                 // 'r' and update count                       
                                                 let count = 0;                       
                                                 for                                     (let i = r; (n / i) >= 1; i = i * r)                       
                                                 count += n / i;                       
                                                 return                                     count;                       
                         }                       
           
                         // Driver code                       
           
                                                 let n = 6, r = 3;                       
                                                 document.write(power(n, r));                       
           
                         // This code is contributed by souravghosh0416.                       
                         </script>                       

输出：

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

THE END

技术文章