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

A P-smooth number is a number whose prime factors are all at most P. For example, 12 = 2 × 2 × 3, so 12 is 3-smooth. Smooth numbers turn up in number theory, in cryptography (some factoring and discrete-log attacks rely on them), and as a neat exercise in prime factorisation.

Problem

Given two numbers n and P, print "Yes" if n is P-smooth, that is, if the largest prime factor of n is less than or equal to P. Otherwise print "No".

Input:  n = 12, P = 3
Output: Yes
12 = 2 × 2 × 3. The largest prime factor is 3, and 3 ≤ 3.

Input:  n = 34, P = 8
Output: No
34 = 2 × 17. The largest prime factor is 17, and 17 > 8.

Approach

Everything comes down to finding the largest prime factor of n. We do that with trial division:

1. Divide out all the 2s. If there were any, the largest prime factor so far is 2.
2. Try the odd numbers 3, 5, 7 ... while i × i ≤ n. Each time i divides n, divide it out completely and remember i.
3. If n is still greater than 1 at the end, what is left is itself a prime, and it is bigger than every factor we found. That is the answer.

Why can we stop at the square root? If n had two prime factors both larger than √n, their product would be larger than n. So after removing all small factors, at most one prime is left, and step 3 catches it.

A quick trace for n = 34: dividing by 2 gives 17, so the best so far is 2. Now i starts at 3, and 3 × 3 = 9 ≤ 17 but 3 does not divide 17. Next i = 5, and 25 > 17, so the loop ends. 17 is left over, so the largest prime factor is 17.

Solution in C++

#include <iostream>
using namespace std;

// Returns the largest prime factor of n (returns 1 for n = 1)
long long largestPrimeFactor(long long n) {
    long long maxPrime = 1;
    while (n % 2 == 0) {
        maxPrime = 2;
        n /= 2;
    }
    for (long long i = 3; i * i <= n; i += 2) {
        while (n % i == 0) {
            maxPrime = i;
            n /= i;
        }
    }
    if (n > 1) maxPrime = n;   // whatever is left is a prime bigger than sqrt(original n)
    return maxPrime;
}

bool isPSmooth(long long n, long long p) {
    return largestPrimeFactor(n) <= p;
}

int main() {
    long long n, p;
    cin >> n >> p;
    cout << (isPSmooth(n, p) ? "Yes" : "No") << endl;
    return 0;
}

Output

12 3  →  Yes
34 8  →  No
1024 2  →  Yes

Complexity

Trial division takes O(√n) time in the worst case (when n is prime) and O(1) extra space. For n up to 10¹² that is at most about a million steps, which is fast.

Notes

• We use long long so that i * i does not overflow for large n.
• By convention 1 has no prime factors, so it counts as P-smooth for every P. The function above returns 1 for n = 1, which gives "Yes".
• If you need to answer many queries for numbers up to a few million, precompute the smallest prime factor of every number with a sieve. Then each number can be factorised in O(log n).

Tip: try to solve the problem yourself before reading the solution. Use the code as a reference to check your approach, and make sure you understand why it works.

More C and CPP solutions All coding problems MCQ practice