C++ P-光滑数或P-可质因数分解数

如果一个数的所有质因数都小于或等于p，则它是p-可质因数分解数。

例如，1620是一个5-光滑数。因为1620的质因数是：2、3和5。可以看到，1620也是一个7-光滑数和11-光滑数。

问题陈述

给定两个数N和P，我们需要检查N是否是一个P-光滑数。

示例

Input −  N = 50, P = 7
Output −  Yes, 50 is a 7-friable number.

解释

50可以被质因数分解为：555*5。

因此，50的质因数只有5。

由于5小于7，50是一个7-可分解或7-平滑数。

Input −  N = 1620, P = 3
Output −  No, 1620 is not a 3-friable number.

说明

1620可以进行质数因式分解为：2233335。

因此，1620的质数因子是2、3和5。

由于5大于3，1620不是一个3可划分或3光滑数。

Input: N = 30, P = 7
Output: Yes, 30 is a 7-friable number.

解释

30可以被质因数分解为：235。

因此，它的质因数是2，3和5。

由于所有的数都小于7，30是一个7-可因子或7-光滑数。

步骤

我们需要对数字N进行质因数分解，然后找出N的最大质因数。

为了对数字进行质因数分解，我们遵循以下方法：

如果数字可以被2整除，将2存为最大质因数，并将N除以2。
将N除以2直到它变成奇数。
现在，从3开始循环，循环次数为N的平方根。当i除以N时，继续将N除以i。
循环结束时，如果N大于2，则它是一个质数。将其存为最大质因数。
比较最大质因数和输入的P。
如果P大于或等于最大质因数，则打印Yes。

伪代码

main() −

初始化N和P。
调用函数is_Pfriable(N,P)。
打印结果。

is_Pfriable(int n, int p) −

largest__prime_factor设为-1
当n能被2整除时 −
- 将n除以2。
- largest_prime_factor设为largest_prime_factor和2的最大值。
对于i从3到n的平方根：
- 当n能被i整除时：
  - largest_prime_factor设为largest_prime_factor和i的最大值。
  - 将n除以i。
如果n大于2：
- 将largest_prime_factor设为largest_prime_factor和n的最大值。
如果p大于等于largest_prime_factor：
- 返回True
否则：
- 返回False

示例

以下是一个用于检查一个数是否为P平滑或P可分性数的C ++程序。

#include <bits/stdc++.h>
using namespace std;
// Function to check if the number n is a P-smooth or P-friable number or not.
bool is_Pfriable(int n, int p){
   //Variable to store the value of the largest prime factor.
    int largest_prime_factor = -1;
    //While loop to divide N till is becomes indivisible by 2.
    //It will also factorize N by all the multiples of 2.
    while ((n % 2)==0){
       //Store the maximum value.
        largest_prime_factor = max(largest_prime_factor, 2);
        //Keep dividing by 2.
        n = n/2;
    }
   //For loop till the square root of n, since factors exist in pairs.
   //Checking for all the possible factor of n.
    for (int i = 3; i <= sqrt(n); i += 2){
      //Eliminate all the multiples of i which could be the factors of n. That is, prime factorize n by i.
        while (n % i == 0){
            largest_prime_factor = max(largest_prime_factor,i);
            //Keep dividing by i.
            n = n / i;
        }
    }
   //If n>2, then it is a prime factor, and thus, the largest prime factor of itself.
    if (n > 2){
       largest_prime_factor = max(largest_prime_factor, n);
    }
    //If p is greater than or equal to the largest prime factor of n, then n is p-friable. Hence, return true.
    if(p>=largest_prime_factor){
        return true;
    }
    //Return false because n is not p-friable.
    return false;
}
int main(){
   //Initialize input
    int n = 56, p = 5;
    //Function call
    //If the function return true, then n is p-friable.
    if (is_Pfriable(n, p)){
       cout<<"Yes, "<<n<<" is a "<<p<<" friable number"<<endl;
    }
    else{
       cout<<"No, "<<n<<" is not a "<<p<<" friable number"<<endl;
    }
    return 0;
}