P-光滑数或P-易碎数-yiteyi-C++库

A. P-光滑数 或 P-易碎数 是一个最大素数因子小于或等于P的整数。给定N和P，我们需要编写一个程序来检查它是否为P-frieble。例如：

null

Input : N = 24   ,  P = 7  Output : YESExplanation : The prime divisors of 24 are 2 and 3 only.               Hence its largest prime factor is 3 which               is less than or equal to 7, it is P-friable. Input : N = 22   ,  P = 5 Output : NOExplanation : The prime divisors are 11 and 2, hence 11>5,              so it is not a P-friable number.

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

方法将是素数分解并存储所有主要因素的最大值。我们首先把这个数除以2，如果它是可除的，然后我们从3迭代到Sqrt（n），得到一个质数除以一个特定数的次数，这个数每次减少n/i，如果它除以n，则存储质数因子i。我们把我们的数n（由质数因子）除以它相应的最小质数因子，直到n变成1。如果在n>2的末尾，这意味着它是一个素数，所以我们也将其存储为一个素数因子。最后将最大因子与p进行比较，以确定它是否是p-光滑数。

C++

                         // CPP program to check if a number is                       
                         // a p-smooth number or not                       
                         #include <iostream>                       
                         #include<math.h>                       
                         using                                     namespace                                     std;                       
           
                         // function to check if number n                       
                         // is a P-smooth number or not                       
                         bool                                     check(                                     int                                     n,                                     int                                     p)                       
                         {                       
                                                 int                                     maximum = -1;                       
                                   
                                                 // prime factorise it by 2                       
                                                 while                                     (!(n % 2))                       
                                                 {                       
                                                 // if the number is divisible by 2                       
                                                 maximum = max(maximum, 2);                       
                                                 n = n/2;                       
                                                 }                       
           
                                                 // check for all the possible numbers                       
                                                 // that can divide it                       
                                                 for                                     (                                     int                                     i = 3; i <=                                     sqrt                                     (n); i += 2)                       
                                                 {                       
                                                 // prime factorize it by i                       
                                                 while                                     (n % i == 0)                       
                                                 {                       
                                                 // stores the maximum if maximum                       
                                                 // and i, if i divides the number                       
                                                 maximum = max(maximum,i);                       
                                                 n = n / i;                       
                                                 }                       
                                                 }                       
           
                                                 // if n at the end is a prime number,                       
                                                 // then it a divisor itself                       
                                                 if                                     (n > 2)                       
                                                 maximum = max(maximum, n);                       
                                   
                                                 return                                     (maximum <= p);                       
                         }                       
           
                         // Driver program to test above function                       
                         int                                     main()                       
                         {                       
                                                 int                                     n = 24, p = 7;                       
                                   
                                                 if                                     (check(n, p))                       
                                                 cout <<                                     "yes"                                     ;                       
                                                 else                       
                                                 cout <<                                     "no"                                     ;                       
                                   
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to check if a number is                       
                         // a p-smooth number or not                       
           
                         import                                     java.lang.*;                       
           
                         class                                     GFG{                       
           
                         // function to check if number n                       
                         // is a P-smooth number or not                       
           
                         static                                     boolean                                     check(                                     int                                     n,                                     int                                     p)                       
                         {                       
                                                 int                                     maximum = -                                     1                                     ;                       
                                   
                                                 // prime factorise it by 2                       
                                                 while                                     ((n %                                     2                                     ) ==                                     0                                     )                       
                                                 {                       
                                                 // if the number is divisible by 2                       
                                                 maximum = Math.max(maximum,                                     2                                     );                       
                                                 n = n/                                     2                                     ;                       
                                                 }                       
           
                                                 // check for all the possible numbers                       
                                                 // that can divide it                       
                                                 for                                     (                                     int                                     i =                                     3                                     ; i <= Math.sqrt(n); i +=                                     2                                     )                       
                                                 {                       
                                                 // prime factorize it by i                       
                                                 while                                     (n % i ==                                     0                                     )                       
                                                 {                       
                                                 // stores the maximum if maximum                       
                                                 // and i, if i divides the number                       
                                                 maximum = Math.max(maximum,i);                       
                                                 n = n / i;                       
                                                 }                       
                                                 }                       
           
                                                 // if n at the end is a prime number,                       
                                                 // then it a divisor itself                       
                                                 if                                     (n >                                     2                                     )                       
                                                 maximum = Math.max(maximum, n);                       
                                   
                                                 return                                     (maximum <= p);                       
                         }                       
           
                         // Driver program to test                       
                         // above function                       
                         public                                     static                                     void                                     main(String[] args)                       
                         {                       
                                                 int                                     n =                                     24                                     , p =                                     7                                     ;                       
                                   
                                                 if                                     (check(n, p))                       
                                                 System.out.println(                                     "yes"                                     );                       
                                                 else                       
                                                 System.out.println(                                     "no"                                     );                       
                                   
                         }                       
                         }                       
           
                         // This code is contributed by                       
                         // Smitha Dinesh Semwal                       

Python3

                         # Python 3 program to                       
                         # check if a number is                       
                         # a p-smooth number or not                       
           
                         import                                     math                       
           
                         # function to check if number n                       
                         # is a P-smooth number or not                       
                         def                                     check(n, p) :                       
           
                                                 maximum                                     =                                     -                                     1                       
                                   
                                                 # prime factorise it by 2                       
                                                 while                                     (                                     not                                     (n                                     %                                     2                                     )):                       
                                   
                                                 # if the number is divisible by 2                       
                                                 maximum                                     =                                     max                                     (maximum,                                     2                                     )                       
                                                 n                                     =                                     int                                     (n                                     /                                     2                                     )                       
                                   
           
                                                 # check for all the possible numbers                       
                                                 # that can divide it                       
                                                 for                                     i                                     in                                     range                                     (                                     3                                     ,                                     int                                     (math.sqrt(n)),                                     2                                     ):                       
                                   
                                                 # prime factorize it by i                       
                                                 while                                     (n                                     %                                     i                                     =                                     =                                     0                                     ) :                       
                                   
                                                 # stores the maximum if maximum                       
                                                 # and i, if i divides the number                       
                                                 maximum                                     =                                     max                                     (maximum,i)                       
                                                 n                                     =                                     int                                     (n                                     /                                     i)                       
                                   
                                   
           
                                                 # if n at the end is a prime number,                       
                                                 # then it a divisor itself                       
                                                 if                                     (n >                                     2                                     ):                       
                                                 maximum                                     =                                     max                                     (maximum, n)                       
                                   
                                                 return                                     (maximum <                                     =                                     p)                       
           
           
                         # Driver program to test above function                       
                         n                                     =                                     24                       
                         p                                     =                                     7                       
                         if                                     (check(n, p)):                       
                                                 print                                     (                                     "yes"                                     )                       
                         else                                     :                       
                                                 print                                     (                                     "no"                                     )                       
           
                         # This code is contributed by                       
                         # Smitha Dinesh Semwal                       

C#

                         // C# program to check if a number is                       
                         // a p-smooth number or not                       
                         using                                     System;                       
           
                         class                                     GFG {                       
           
                                                 // function to check if number n                       
                                                 // is a P-smooth number or not                       
                                   
                                                 static                                     bool                                     check(                                     int                                     n,                                     int                                     p)                       
                                                 {                       
                                                 int                                     maximum = -1;                       
                                   
                                                 // prime factorise it by 2                       
                                                 while                                     ((n % 2) == 0)                       
                                                 {                       
                                                 // if the number is divisible by 2                       
                                                 maximum = Math.Max(maximum, 2);                       
                                                 n = n / 2;                       
                                                 }                       
                                   
                                                 // check for all the possible numbers                       
                                                 // that can divide it                       
                                                 for                                     (                                     int                                     i = 3; i <= Math.Sqrt(n); i += 2)                       
                                                 {                       
                                                 // prime factorize it by i                       
                                                 while                                     (n % i == 0)                       
                                                 {                       
                                                 // stores the maximum if maximum                       
                                                 // and i, if i divides the number                       
                                                 maximum = Math.Max(maximum, i);                       
                                                 n = n / i;                       
                                                 }                       
                                                 }                       
                                   
                                                 // if n at the end is a prime number,                       
                                                 // then it a divisor itself                       
                                                 if                                     (n > 2)                       
                                                 maximum = Math.Max(maximum, n);                       
                                   
                                                 return                                     (maximum <= p);                       
                                                 }                       
                                   
                                                 // Driver program to test                       
                                                 // above function                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 int                                     n = 24, p = 7;                       
                                   
                                                 if                                     (check(n, p))                       
                                                 Console.Write(                                     "yes"                                     );                       
                                                 else                       
                                                 Console.Write(                                     "no"                                     );                       
                                   
                                                 }                       
                         }                       
           
                         // This code is contributed by vt_m.                       

PHP

                         <?php                       
                         // PHP program to check if a number is                       
                         // a p-smooth number or not                       
           
                         // function to check if number n                       
                         // is a P-smooth number or not                       
                         function                                     check(                                     $n                                     ,                                     $p                                     )                       
                         {                       
                                                 $maximum                                     = -1;                       
                                   
                                                 // prime factorise it by 2                       
                                                 while                                     (!(                                     $n                                     % 2))                       
                                                 {                       
                                                 // if the number is                       
                                                 // divisible by 2                       
                                                 $maximum                                     = max(                                     $maximum                                     , 2);                       
                                                 $n                                     =                                     $n                                     / 2;                       
                                                 }                       
           
                                                 // check for all the possible                       
                                                 // numbers that can divide it                       
                                                 for                                     (                                     $i                                     = 3;                                     $i                                     <= sqrt(                                     $n                                     );                                     $i                                     += 2)                       
                                                 {                       
                                   
                                                 // prime factorize it by i                       
                                                 while                                     (                                     $n                                     %                                     $i                                     == 0)                       
                                                 {                       
                                                 // stores the maximum if maximum                       
                                                 // and i, if i divides the number                       
                                                 $maximum                                     = max(                                     $maximum                                     ,                                     $i                                     );                       
                                                 $n                                     =                                     $n                                     /                                     $i                                     ;                       
                                                 }                       
                                                 }                       
           
                                                 // if n at the end is a prime number,                       
                                                 // then it a divisor itself                       
                                                 if                                     (                                     $n                                     > 2)                       
                                                 $maximum                                     = max(                                     $maximum                                     ,                                     $n                                     );                       
                                   
                                                 return                                     (                                     $maximum                                     <=                                     $p                                     );                       
                         }                       
           
                         // Driver Code                       
                         $n                                     = 24;                                     $p                                     = 7;                       
                                   
                         if                                     (check(                                     $n                                     ,                                     $p                                     ))                       
                                                 echo                                     (                                     "yes"                                     );                       
                         else                       
                                                 echo                                     (                                     "no"                                     );                       
                                   
                         // This code is contributed by Ajit.                       
                         ?>                       

Javascript

                         <script>                       
                         // Javascript program to check if a number is                       
                         // a p-smooth number or not                       
           
                                                 // function to check if number n                       
                                                 // is a P-smooth number or not                       
                                                 function                                     check(n, p)                       
                                                 {                       
                                                 let maximum = -1;                       
                                   
                                                 // prime factorise it by 2                       
                                                 while                                     (!(n % 2))                       
                                                 {                       
                                   
                                                 // if the number is divisible by 2                       
                                                 maximum = Math.max(maximum, 2)                       
                                                 n = n/2;                       
                                                 }                       
           
                                                 // check for all the possible numbers                       
                                                 // that can divide it                       
                                                 var                                     i;                       
                                                 for                                     (i = 3; i*i <= n; i += 2)                       
                                                 {                       
                                   
                                                 // prime factorize it by i                       
                                                 while                                     (n % i == 0)                       
                                                 {                       
                                   
                                                 // stores the maximum if maximum                       
                                                 // and i, if i divides the number                       
                                                 maximum = Math.max(maximum, i);                       
                                                 n = n / i;                       
                                                 }                       
                                                 }                       
           
                                                 // if n at the end is a prime number,                       
                                                 // then it a divisor itself                       
                                                 if                                     (n > 2)                       
                                                 maximum = Math.max(maximum, n);                       
           
                                                 if                                     (maximum <= p)                       
                                                 return                                     true                                     ;                       
                                                 else                       
                                                 return                                     false                                     ;                       
                                                 }                       
                                   
                                                 // Driver Code                       
                                                 let n = 24, p = 7;                       
                                                 if                                     (check(n, p))                       
                                                 document.write(                                     "yes"                                     );                       
                                                 else                       
                                                 document.write(                                     "no"                                     );                       
                                   
                                                 // This code is contributed by ajaykrsharma132.                       
                         </script>                       

输出：

yes

参考 : http://oeis.org/wiki/P-smooth_numbers

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

THE END

技术文章