P-光滑数或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 可以质因数分解为：5*5*5*5。

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

由于 5 小于 7，因此 50 是一个 7-易碎数或 7-光滑数。

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

解释

1620 可以质因数分解为：2*2*3*3*3*3*5。

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

由于 5 大于 3，因此 1620 不是一个 3-易碎数或 3-光滑数。

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

解释

30 可以质因数分解为：2*3*5。

因此，质因数是 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 -> maximum(largest_prime_factor, 2)

• 对于 i->3 到 i->square_root(n)

• 当 n 可以被 i 整除时

• largest_prime_factor -> maximum(largest_prime_factor, i)

• 将 n 除以 i

• 如果 n > 2

• largest_prime_factor -> maximum(largest_prime_factor, i)

• 如果 p >= largest_prime_factor

• 返回 True

• 否则

• 返回 False

示例

下面是一个 C++ 程序，用于检查一个数是否为 P-光滑数或 P-易碎数。

#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;
}

输出

No, 56 is not a 5 friable number

分析

时间复杂度 − O(sqrt ( N ) * log N)，

复杂度是这样的，因为 for 循环。

外部 for 循环的复杂度为 sqrt(N)。内部循环的复杂度为对数。因此，最终结果是它们的乘积。

空间复杂度 − O(1) [常数]

空间复杂度是常数，因为我们没有使用任何额外的空间。

结论

在本文中，我们讨论了 P-光滑数或 P-易碎数的概念。我们解决了给定数字是否为 P-易碎数的问题。我们通过一些示例了解了问题陈述，然后查看了方法、伪代码和 C++ 程序。