强数-yiteyi-C++库

如果一个数n的每一个素因子p ^2. 也将其分开。例如：-36是一个强大的数字。它既可以被3整除，也可以被3的平方整除，即9。前几个强有力的数字是： 1, 4, 8, 9, 16, 25, 27, 32, 36, 49, 64 …. 给定一个数字n，我们的任务是检查它是否强大。 例如：

null

Input: 27Output: YESInput: 32Output: YESInput: 12Output: NO

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

这个想法是基于这样一个事实：如果一个数n是强大的，那么它的所有素因子及其平方都应该可以被n整除求给定数的所有素数因子对于每一个素数因子，我们找到它除以n的最高次幂。如果我们找到一个素数因子，它的最高次幂是1，我们返回false。如果所有素数因子的最高除法大于1，则返回true。下面是上述想法的实现。

C++

                         // C++ program to find if a number is powerful or not.                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // function to check if the number is powerful                       
                         bool                                     isPowerful(                                     int                                     n)                       
                         {                       
                                                 // First divide the number repeatedly by 2                       
                                                 while                                     (n % 2 == 0) {                       
                                                 int                                     power = 0;                       
                                                 while                                     (n % 2 == 0) {                       
                                                 n /= 2;                       
                                                 power++;                       
                                                 }                       
           
                                                 // If only 2^1 divides n (not higher powers),                       
                                                 // then return false                       
                                                 if                                     (power == 1)                       
                                                 return                                     false                                     ;                       
                                                 }                       
           
                                                 // if n is not a power of 2 then this loop will execute                       
                                                 // repeat above process                       
                                                 for                                     (                                     int                                     factor = 3; factor <=                                     sqrt                                     (n); factor += 2) {                       
                                                 // Find highest power of "factor" that divides n                       
                                                 int                                     power = 0;                       
                                                 while                                     (n % factor == 0) {                       
                                                 n = n / factor;                       
                                                 power++;                       
                                                 }                       
           
                                                 // If only factor^1 divides n (not higher powers),                       
                                                 // then return false                       
                                                 if                                     (power == 1)                       
                                                 return                                     false                                     ;                       
                                                 }                       
           
                                                 // n must be 1 now if it is not a prime numenr.                       
                                                 // Since prime numbers are not powerful, we return                       
                                                 // false if n is not 1.                       
                                                 return                                     (n == 1);                       
                         }                       
           
                         // Driver program to test above function                       
                         int                                     main()                       
                         {                       
                                                 isPowerful(20) ? cout <<                                     "YES"                                     : cout <<                                     "NO"                                     ;                       
                                                 isPowerful(27) ? cout <<                                     "YES"                                     : cout <<                                     "NO"                                     ;                       
           
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to find if a                       
                         // number is powerful or not.                       
           
                         class                                     GFG {                       
                                                 // function to check if the                       
                                                 // number is powerful                       
                                                 static                                     boolean                                     isPowerful(                                     int                                     n)                       
                                                 {                       
                                                 // First divide the number                       
                                                 // repeatedly by 2                       
                                                 while                                     (n %                                     2                                     ==                                     0                                     ) {                       
                                                 int                                     power =                                     0                                     ;                       
                                                 while                                     (n %                                     2                                     ==                                     0                                     ) {                       
                                                 n /=                                     2                                     ;                       
                                                 power++;                       
                                                 }                       
           
                                                 // If only 2^1 divides n (not higher powers),                       
                                                 // then return false                       
                                                 if                                     (power ==                                     1                                     )                       
                                                 return                                     false                                     ;                       
                                                 }                       
           
                                                 // if n is not a power of 2 then this loop will execute                       
                                                 // repeat above process                       
                                                 for                                     (                                     int                                     factor =                                     3                                     ; factor <= Math.sqrt(n); factor +=                                     2                                     ) {                       
                                                 // Find highest power of "factor" that divides n                       
                                                 int                                     power =                                     0                                     ;                       
                                                 while                                     (n % factor ==                                     0                                     ) {                       
                                                 n = n / factor;                       
                                                 power++;                       
                                                 }                       
           
                                                 // If only factor^1 divides n (not higher powers),                       
                                                 // then return false                       
                                                 if                                     (power ==                                     1                                     )                       
                                                 return                                     false                                     ;                       
                                                 }                       
           
                                                 // n must be 1 now if it is not a prime numenr.                       
                                                 // Since prime numbers are not powerful, we return                       
                                                 // false if n is not 1.                       
                                                 return                                     (n ==                                     1                                     );                       
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 if                                     (isPowerful(                                     20                                     ))                       
                                                 System.out.print(                                     "YES"                                     );                       
                                                 else                       
                                                 System.out.print(                                     "NO"                                     );                       
                                                 if                                     (isPowerful(                                     27                                     ))                       
                                                 System.out.print(                                     "YES"                                     );                       
                                                 else                       
                                                 System.out.print(                                     "NO"                                     );                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Anant Agarwal.                       

Python3

                         # Python program to find                       
                         # if a number is powerful or not.                       
                         import                                     math                       
           
                         # function to check if                       
                         # the number is powerful                       
                         def                                     isPowerful(n):                       
           
                                                 # First divide the number repeatedly by 2                       
                                                 while                                     (n                                     %                                     2                                     =                                     =                                     0                                     ):                       
           
                                                 power                                     =                                     0                       
                                                 while                                     (n                                     %                                     2                                     =                                     =                                     0                                     ):                       
                                   
                                                 n                                     =                                     n                                     /                                     /                                     2                       
                                                 power                                     =                                     power                                     +                                     1                       
                                   
                                   
                                                 # If only 2 ^ 1 divides                       
                                                 # n (not higher powers),                       
                                                 # then return false                       
                                                 if                                     (power                                     =                                     =                                     1                                     ):                       
                                                 return                                     False                       
                                   
                                   
                                                 # if n is not a power of 2                       
                                                 # then this loop will execute                       
                                                 # repeat above process                       
                                                 for                                     factor                                     in                                     range                                     (                                     3                                     ,                                     int                                     (math.sqrt(n))                                     +                                     1                                     ,                                     2                                     ):                       
                                   
                                                 # Find highest power of                       
                                                 # "factor" that divides n                       
                                                 power                                     =                                     0                       
                                                 while                                     (n                                     %                                     factor                                     =                                     =                                     0                                     ):                       
                                   
                                                 n                                     =                                     n                                     /                                     /                                     factor                       
                                                 power                                     =                                     power                                     +                                     1                       
                                   
                                   
                                                 # If only factor ^ 1 divides                       
                                                 # n (not higher powers),                       
                                                 # then return false                       
                                                 if                                     (power                                     =                                     =                                     1                                     ):                       
                                                 return                                     false                       
                                   
                                   
                                                 # n must be 1 now if it                       
                                                 # is not a prime numenr.                       
                                                 # Since prime numbers are                       
                                                 # not powerful, we return                       
                                                 # false if n is not 1.                       
                                                 return                                     (n                                     =                                     =                                     1                                     )                       
           
                         # Driver code                       
           
                         print                                     (                                     "YES"                                     if                                     isPowerful(                                     20                                     )                                     else                                     "NO"                                     )                       
                         print                                     (                                     "YES"                                     if                                     isPowerful(                                     27                                     )                                     else                                     "NO"                                     )                       
           
           
                         # This code is contributed                       
                         # by Anant Agarwal.                       

C#

                         // C# program to find if a                       
                         // number is powerful or not.                       
                         using                                     System;                       
           
                         class                                     GFG {                       
           
                                                 // function to check if the                       
                                                 // number is powerful                       
                                                 static                                     bool                                     isPowerful(                                     int                                     n)                       
                                                 {                       
                                                 // First divide the number                       
                                                 // repeatedly by 2                       
                                                 while                                     (n % 2 == 0) {                       
                                                 int                                     power = 0;                       
                                                 while                                     (n % 2 == 0) {                       
                                                 n /= 2;                       
                                                 power++;                       
                                                 }                       
           
                                                 // If only 2^1 divides n                       
                                                 // (not higher powers),                       
                                                 // then return false                       
                                                 if                                     (power == 1)                       
                                                 return                                     false                                     ;                       
                                                 }                       
           
                                                 // if n is not a power of 2 then                       
                                                 // this loop will execute repeat                       
                                                 // above process                       
                                                 for                                     (                                     int                                     factor = 3; factor <= Math.Sqrt(n); factor += 2) {                       
                                                 // Find highest power of "factor"                       
                                                 // that divides n                       
                                                 int                                     power = 0;                       
                                                 while                                     (n % factor == 0) {                       
                                                 n = n / factor;                       
                                                 power++;                       
                                                 }                       
           
                                                 // If only factor^1 divides n                       
                                                 // (not higher powers), then                       
                                                 // return false                       
                                                 if                                     (power == 1)                       
                                                 return                                     false                                     ;                       
                                                 }                       
           
                                                 // n must be 1 now if it is not                       
                                                 // a prime numenr.                       
                                                 // Since prime numbers are not                       
                                                 // powerful, we return false if                       
                                                 // n is not 1.                       
                                                 return                                     (n == 1);                       
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 if                                     (isPowerful(20))                       
                                                 Console.WriteLine(                                     "YES"                                     );                       
                                                 else                       
                                                 Console.WriteLine(                                     "NO"                                     );                       
           
                                                 if                                     (isPowerful(27))                       
                                                 Console.WriteLine(                                     "YES"                                     );                       
                                                 else                       
                                                 Console.WriteLine(                                     "NO"                                     );                       
                                                 }                       
                         }                       
           
                         // This code is contributed by vt_m.                       

PHP

                         <?php                       
                         // PHP program to find if a                       
                         // number is powerful or not                       
           
                         // function to check if                       
                         // the number is powerful                       
                         function                                     isPowerful(                                     $n                                     )                       
                         {                       
                                                 // First divide the                       
                                                 // number repeatedly by 2                       
                                                 while                                     (                                     $n                                     % 2 == 0)                       
                                                 {                       
                                                 $power                                     = 0;                       
                                                 while                                     (                                     $n                                     % 2 == 0)                       
                                                 {                       
                                                 $n                                     /= 2;                       
                                                 $power                                     ++;                       
                                                 }                       
                                   
                                                 // If only 2^1 divides                       
                                                 // n (not higher powers),                       
                                                 // then return false                       
                                                 if                                     (                                     $power                                     == 1)                       
                                                 return                                     false;                       
                                                 }                       
           
                                                 // if n is not a power of 2                       
                                                 // then this loop will execute                       
                                                 // repeat above process                       
                                                 for                                     (                                     $factor                                     = 3;                       
                                                 $factor                                     <= sqrt(                                     $n                                     );                       
                                                 $factor                                     += 2)                       
                                                 {                       
                                                 // Find highest power of                       
                                                 // "factor" that divides n                       
                                                 $power                                     = 0;                       
                                                 while                                     (                                     $n                                     %                                     $factor                                     == 0)                       
                                                 {                       
                                                 $n                                     =                                     $n                                     /                                     $factor                                     ;                       
                                                 $power                                     ++;                       
                                                 }                       
           
                                                 // If only factor^1 divides                       
                                                 // n (not higher powers),                       
                                                 // then return false                       
                                                 if                                     (                                     $power                                     == 1)                       
                                                 return                                     false;                       
                                                 }                       
           
                                                 // n must be 1 now if it is                       
                                                 // not a prime number. Since                       
                                                 // prime numbers are not powerful,                       
                                                 // we return false if n is not 1.                       
                                                 return                                     (                                     $n                                     == 1);                       
                         }                       
           
                         // Driver Code                       
                         $d                                     = isPowerful(20) ?                       
                                                 "YES"                                     :                       
                                                 "NO"                                     ;                       
                                                 echo                                     $d                                     ;                       
                         $d                                     = isPowerful(27) ?                       
                                                 "YES"                                     :                       
                                                 "NO"                                     ;                       
                                                 echo                                     $d                                     ;                       
           
                         // This code is contributed by ajit.                       
                         ?>                       

Javascript

                         <script>                       
           
                         // Javascript program to find if a                       
                         // number is powerful or not.                       
           
                                                 // function to check if the                       
                                                 // number is powerful                       
                                                 function                                     isPowerful(n)                       
                                                 {                       
                                                 // First divide the number                       
                                                 // repeatedly by 2                       
                                                 while                                     (n % 2 == 0) {                       
                                                 let power = 0;                       
                                                 while                                     (n % 2 == 0) {                       
                                                 n /= 2;                       
                                                 power++;                       
                                                 }                       
                                   
                                                 // If only 2^1 divides n (not higher powers),                       
                                                 // then return false                       
                                                 if                                     (power == 1)                       
                                                 return                                     false                                     ;                       
                                                 }                       
                                   
                                                 // if n is not a power of 2 then this loop will execute                       
                                                 // repeat above process                       
                                                 for                                     (let factor = 3; factor <= Math.sqrt(n); factor += 2) {                       
                                                 // Find highest power of "factor" that divides n                       
                                                 let power = 0;                       
                                                 while                                     (n % factor == 0) {                       
                                                 n = n / factor;                       
                                                 power++;                       
                                                 }                       
                                   
                                                 // If only factor^1 divides n (not higher powers),                       
                                                 // then return false                       
                                                 if                                     (power == 1)                       
                                                 return                                     false                                     ;                       
                                                 }                       
                                   
                                                 // n must be 1 now if it is not a prime numenr.                       
                                                 // Since prime numbers are not powerful, we return                       
                                                 // false if n is not 1.                       
                                                 return                                     (n == 1);                       
                                                 }                       
           
                         // Driver code to test above methods                       
           
                                                 if                                     (isPowerful(20))                       
                                                 document.write(                                     "YES"                                     +                                     "<br>"                                     );                       
                                                 else                       
                                                 document.write(                                     "NO"                                     +                                     "<br>"                                     );                       
                                                 if                                     (isPowerful(27))                       
                                                 document.write(                                     "YES"                                     +                                     "<br>"                                     );                       
                                                 else                       
                                                 document.write(                                     "NO"                                     +                                     "<br>"                                     );                       
                                   
                         // This code is contributed by avijitmondal1998.                       
                         </script>                       

输出：

NOYES

参考资料： https://en.wikipedia.org/wiki/Powerful_number 本文由 严酷的阿加瓦尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用贡献极客。组织或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

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

THE END

技术文章