The prime factors of an integer n > 1 are the prime numbers that multiply together to make n. Every such n has a unique factorization (ignoring order).
Remember
84 = 2 × 2 × 3 × 7
30 = 2 × 3 × 5
17 = 17 (already prime)
Method idea: trial division
peel small primes from n until only 1 remains
n
Prime factors
84
2, 2, 3, 7
100
2, 2, 5, 5
13
13
Approach
How to Find Prime Factors in C++
Four clear steps — then pick a simple scan or an O(√n) version.
Require n > 1.
While n is even, print 2 and set n /= 2.
Try odd candidates i = 3, 5, 7, …; whenever i divides n, print i and divide.
If n > 1 remains, that leftover is a prime factor — print it.
Method
Idea
Time
Best for
Simple trial
Try factors while i <= n
O(n)
First explanation
√n trial
Loop while i * i <= n
O(√n)
Interview / practical code
Pseudocode
Pseudocode
function PrintPrimeFactors(n):
if n <= 1: return
while n % 2 == 0:
print 2
n = n / 2
i = 3
while i * i <= n:
while n % i == 0:
print i
n = n / i
i = i + 2
if n > 1:
print n
Reference
Cheat Sheet
Keep these facts handy while writing the program.
Topic
Detail
Input
n > 1
Factor 2
Peel first (only even prime)
Odd loop
Step i by 2
Leftover
If n > 1 after loops, print n
Repeats
Print the same prime each time it divides
Classic check
84 → 2 2 3 7
Try it
Live Preview
Enter an integer greater than 1 to see its prime factorization.
Integers from 2 to 1000000. Tap a chip or type a value.
Result
n = 84
Prime factors: 2 × 2 × 3 × 7
Trace
Worked Walkthrough — n = 84
Peel factors from smallest to largest until only 1 remains.
Calculation
84 is even → factor 2, n = 42
42 is even → factor 2, n = 21
Try i = 3:
21 % 3 == 0 → factor 3, n = 7
i = 5: 5*5 > 7 → stop odd loop
Leftover n = 7 > 1 → factor 7
Prime factors: 2 × 2 × 3 × 7
Code
C++ Programs
Start with the simple trial loop so every step is obvious. Then use the √n version for the usual interview answer.
Example 1 — Simple Trial
Try candidates from 2 upward while dividing n down to 1.
C++
#include <iostream>
using namespace std;
void printPrimeFactors(int n)
{
if (n <= 1)
{
cout << "Enter an integer greater than 1." << endl;
return;
}
cout << "Prime factors of " << n << ": ";
for (int i = 2; i <= n; i++)
{
while (n % i == 0)
{
cout << i << " ";
n /= i;
}
}
cout << endl;
}
int main()
{
printPrimeFactors(84);
return 0;
}
Output
Prime factors of 84: 2 2 3 7
How It Works
Reject n <= 1 — factorization needs an integer greater than 1.
Outer loop tries each candidate i starting at 2.
Inner while peels every copy of that factor from n.
Because smaller factors are removed first, each printed i is prime.
When n becomes 1, the loop ends and the factorization is complete.
Example 2 — √n Trial
Handle 2 first, then odd factors up to √n, then print any leftover prime.
C++
#include <iostream>
using namespace std;
void printPrimeFactors(int n)
{
if (n <= 1)
{
cout << "Enter an integer greater than 1." << endl;
return;
}
cout << "Prime factors of " << n << ": ";
while (n % 2 == 0)
{
cout << "2 ";
n /= 2;
}
for (long long i = 3; i * i <= n; i += 2)
{
while (n % i == 0)
{
cout << i << " ";
n /= i;
}
}
if (n > 1)
{
cout << n;
}
cout << endl;
}
int main()
{
printPrimeFactors(84);
printPrimeFactors(13);
return 0;
}
Output
Prime factors of 84: 2 2 3 7
Prime factors of 13: 13
How It Works
Peel all factors of 2 first so the rest of the search can skip even numbers.
Odd loop runs only while i * i <= n — no need to go past √n.
Use long long for i so i * i does not overflow for larger n.
After the loop, any leftover n > 1 is itself a prime factor.
Same answers as Example 1, typically much faster for larger n.
Edge Cases & Pitfalls
Check these before calling the solution done.
n ≤ 1
Invalid input
Factorization is defined for integers greater than 1.
Prime n
Print itself
If no small factors exist, the leftover n is the answer.
Powers
Repeat factors
8 = 2 × 2 × 2. Keep dividing until that prime no longer divides.
√n stop
Do not skip leftover
Always print remaining n > 1 after the square-root loop.
Analysis
Time and Space Complexity
Program
Time
Extra space
Simple trial
O(n)
O(1)
√n trial
O(√n)
O(1)
Prefer the √n method in interviews. Storing factors in a vector would add space proportional to the number of prime factors with multiplicity.
Remember
Key Takeaways
Definition: primes that multiply to n (unique up to order).
Method: trial division — peel small primes from n.
Speedup: handle 2, then odds up to √n, then leftover.
Test set: 84 → 2×2×3×7; 13 → 13; 100 → 2×2×5×5.
One line: divide out small primes from n; whatever is left (if > 1) is also prime.
Frequently Asked Questions
The prime numbers that multiply together to make n. For example, 84 = 2 × 2 × 3 × 7.
Trial division: peel off factor 2, then try odd candidates while dividing n. If anything greater than 1 remains, that leftover is a prime factor.
2 is the only even prime. Removing all factors of 2 first lets the rest of the loop step by 2.
The loops find no small factors, so the final leftover equals the original n and is printed once.
A simple scan up to n is O(n) in the worst case. Stopping at √n is O(√n). Extra space is O(1) aside from storing the factors you print.
