C++ program to check if a number is P Smooth

 C++ program to check if a number is P Smooth

P-Smooth Number : A number is a smooth number if its largest prime factor is less than or equal to P. Given n and P, we need to write a program to check whether it is P-Smooth or not.

Solution

#include <iostream>
using namespace std;
 
int lpf(int n){
	int Max = -1;
	while(n % 2 == 0){
		Max = 2;
		n = n / 2;
	}
	for(int i = 3; i * i <= n; i += 2){
		while(n % i == 0){
			Max = i;
			n = n / i;
		}
	}
	if(n > 2 && n > Max)
		Max = n;
	return Max;
}
 
bool psmooth(int n, int p){
	if(lpf(n) <= p)
		return true;
	return false;
}
 
int main() {
	// your code goes here
	int n, p;
	cin>>n>>p;
	if(psmooth(n, p))
		cout<<"Yes";
	else
		cout<<"No";
	return 0;
}

Output

Input : n = 12  ,  P = 3  

Output : Yes

Explanation : The prime factors of 12 are  2, 2  and 3 Hence its largest prime factor is 3 which is less than or equal to 3, so it is P-Smooth number. 

Input : n = 34   ,  P = 8

Output : No

Explanation : The prime factors of 34 are 17 and 2, hence 17>8,so it is not a P-Smooth number. 

If you Have Any doubts join the discussions below , our moderators will reach to your doubts .