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++ 程式。