Definition
Prime ÷ n
Primes that divide n evenly.
Find Prime Factors in C++
Overview
What You’ll Learn
Prime factors are the prime numbers that multiply to make n. For example, 56 = 2 × 2 × 2 × 7. This tutorial covers trial division (simple and sqrt-optimized), a live factorizer, worked C++ examples, edge cases, and complexity.
Trial Division
Peel factors
Divide out each i while it fits.
Repeats
Inner while
Capture 2, 2, 2 in 56.
Sqrt Speedup
Fewer checks
Stop near sqrt; print leftover.
Live Preview
Try 56 / 360
See factors and product check.
n >= 2
Domain
Factorization starts at 2.
Introduction
Prime factorization rewrites an integer n >= 2 as a product of primes. By the fundamental theorem of arithmetic, that product is unique up to order.
Interviews usually want trial division: try candidate divisors in increasing order, divide out each one completely, then move on. A faster variant peels 2s first, then odd candidates up to sqrt(x), and prints any leftover prime.
Why it matters?
It is a core number-theory skill that feeds prime checks, GCD tricks, and many coding-interview warm-ups.
Key Highlights
Unique Product
One prime multiset per n > 1.
Peel Completely
Inner while for repeats.
n >= 2
Reject 0, 1, negatives.
Sorted Output
Factors rise naturally.
In short: for each candidate i, divide out every copy of i; leftovers are primes.
Foundation
📝 Problem & Approach
Given an integer n >= 2, print (or return) its prime factors in non-decreasing order.
c++
// 56 -> 2 2 2 7
// 17 -> 17 (already prime)
// 360 -> 2 2 2 3 3 5
// 1 -> invalid for this tutorialInputs & Outputs
| Item | Type | Description |
|---|---|---|
n | int | Integer to factor (n >= 2). |
| Printed factors | ints | Prime multiset in ascending order. |
| Optional vector | std::vector<int> | Same factors as a returned collection. |
Minimal workflow
Pseudocode
procedure display_prime_factors(n):
if n < 2:
stop
x = n
for i from 2 while i <= x:
while x mod i == 0:
output i
x = x / iMethod comparison
| Method | Idea | Notes |
|---|---|---|
| Naive trial | Try i = 2, 3, … while i <= x | Clearest for beginners |
| Sqrt trial | Peel 2s; odds while i*i <= x | Fewer checks; leftover prime |
| Sieve helpers | Precompute primes for many n | Better for bulk queries |
Cheat Sheet
⚡ Quick Reference
| Goal | Pattern |
|---|---|
| Validate | if (n < 2) return; |
| Divide out i | while (x % i == 0) { …; x /= i; } |
| Peel twos | while (x % 2 == 0) |
| Odd candidates | i = 3; i += 2 |
| Sqrt bound | while ((long) i * i <= x) |
| Leftover prime | if (x > 1) std::cout << x; |
Compare
📋 Naive vs Fast vs Return Vector
Same factorization — different packaging.
Naive
i <= xEasiest to dry-run
Fast
i*i <= xInterview upgrade path
List return
factors.Add(i)Reuse factors later
No is_prime?
order peelsComposites never survive
Context
When This Problem Shows Up
Reach for factorization whenever you need the prime building blocks of n.
Interview warm-ups
Classic trial-division prompt.
Bridge to primes
Same divisor mindset as prime checks.
GCD / LCM prep
Factors explain shared primes.
Teaching uniqueness
Show the fundamental theorem live.
Not for n < 2
Reject 0, 1, and negatives here.
Key benefit: one nested-loop pattern that explains why composites never need an explicit is_prime helper.
Interactive
🔮 Live Preview
Uses optimized factorization (2s first, then odd divisors) and verifies the product.
Hands-On
Examples Gallery
Three complete C++ programs — simple trial division for 56, a faster sqrt-style version, and a helper that returns factors as a vector. Click View Output to reveal sample console results.
📚 Getting Started
Readable nested loops that peel every factor.
Example 1 — Straightforward Trial Division
Simple readable function using nested loops.
c++
#include <iostream>
bool dividesEvenly(int a, int b) {
return a % b == 0;
}
void displayPrimeFactors(int n) {
if (n < 2) {
std::cout << "Enter an integer n >= 2 (got " << n << ").\n";
return;
}
std::cout << "Prime factors of " << n << " are: ";
int x = n;
int i = 2;
while (i <= x) {
while (dividesEvenly(x, i)) {
std::cout << i << " ";
x /= i;
}
i++;
}
std::cout << "\n";
}
int main() {
displayPrimeFactors(56);
return 0;
}How It Works
Starting at i = 2, the inner while removes three factors of 2, leaving 7. Then i reaches 7, which divides once, and x becomes 1.
⚡ Faster Trial Division
Fewer candidates with a sqrt bound and a leftover prime.
Example 2 — Faster Trial (2 Then Odd Up to Sqrt)
Fewer divisor checks by handling 2 separately and testing odd candidates only.
c++
#include <iostream>
void displayPrimeFactorsFast(int n) {
if (n < 2) {
std::cout << "Enter an integer n >= 2 (got " << n << ").\n";
return;
}
std::cout << "Prime factors of " << n << " are: ";
int x = n;
while (x % 2 == 0) {
std::cout << "2 ";
x /= 2;
}
int i = 3;
while ((long long) i * i <= x) {
while (x % i == 0) {
std::cout << i << " ";
x /= i;
}
i += 2;
}
if (x > 1) {
std::cout << x << " ";
}
std::cout << "\n";
}
int main() {
displayPrimeFactorsFast(56);
return 0;
}How It Works
After removing factors of 2, x is 7. Because 3 * 3 > 7, the odd loop stops and the leftover 7 is printed.
Example 3 — Return Factors as a Vector
Collect factors for reuse instead of only printing them.
c++
#include <iostream>
#include <vector>
#include <string>
std::vector<int> primeFactors(int n) {
std::vector<int> factors;
if (n < 2) {
return factors;
}
int x = n;
while (x % 2 == 0) {
factors.push_back(2);
x /= 2;
}
int i = 3;
while ((long long) i * i <= x) {
while (x % i == 0) {
factors.push_back(i);
x /= i;
}
i += 2;
}
if (x > 1) {
factors.push_back(x);
}
return factors;
}
std::string joinFactors(const std::vector<int>& factors) {
std::string out;
for (size_t i = 0; i < factors.size(); i++) {
if (i > 0) {
out += ", ";
}
out += std::to_string(factors[i]);
}
return out;
}
int main() {
int values[] = { 56, 17, 360 };
int count = sizeof(values) / sizeof(values[0]);
for (int i = 0; i < count; i++) {
int value = values[i];
std::cout << value << " -> [" << joinFactors(primeFactors(value)) << "]\n";
}
return 0;
}How It Works
Same peeling logic as Example 2, but factors land in a vector you can product-check, count, or pass to other helpers.
🧠 How the Algorithm Decides
1
Require n >= 2
Factorization is undefined for smaller values here.
Guard
2
Try candidate i
Start at 2 (or peel 2s, then odds).
Search
3
Divide while divisible
Print/append i and shrink x each time.
Peel
=
Finish when x is 1
(Or print leftover prime in the fast version.)
Trace
🔎 Worked Walkthrough — 56
Trace the naive peel for n = 56.
| i | x before | Action | x after |
|---|---|---|---|
2 | 56 | print 2 three times | 7 |
3 … 6 | 7 | no division | 7 |
7 | 7 | print 7 once | 1 |
Result: 2 2 2 7. Product check: 2×2×2×7 = 56.
Use Cases
Where prime factorization shows up beyond the interview prompt.
1. Interview Classics
Trial division and nested loops.
Example: factor 56.
2. Teaching Uniqueness
One prime product per n > 1.
Example: facts callout.
3. Bridge to Primes
Same divisor thinking as is_prime.
Example: next page.
4. GCD / LCM Prep
Shared primes explain GCD.
Example: related GCD.
5. Reusable Lists
Return factors for later math.
Example: Example 3.
6. Bulk Queries
Sieve primes when factoring many n.
Example: notes tip.
Pro Tip: say “I’ll peel smallest factors completely so composites never need an is_prime call” before coding.
Advantages
Why trial division works well for beginners and interviews.
1. Easy to Trace
Dry-run 56 on paper and watch x shrink.
2. No Extra is_prime
Ascending order keeps composites from sticking.
3. Clear Upgrade Path
Move from naive to sqrt when asked.
4. Sorted Naturally
Factors emerge in non-decreasing order.
Pro Tip: start with the naive version in interviews, then offer the sqrt optimization unprompted.
Usage Tips
Small habits that keep factorization interview-ready.
1. Guard n >= 2
Reject invalid domains early.
2. Peel Completely
Inner while captures repeated primes.
3. Product-Check
Multiply factors back to n for confidence.
4. Remember Leftover
Fast version must print x if x > 1.
5. Return Vectors When Useful
Printing alone is fine; vectors compose better.
Pro Tip: sanity-check 56, 17, and 360 — if those three match, your peel logic is solid.
Common Pitfalls
Mistakes that commonly break prime-factor programs.
1. Skipping the Inner While
Printing each divisor only once.
→ Keep dividing while x % i == 0.
2. Forgetting Leftover Prime
Sqrt version stops and drops the last prime.
→ if x > 1: print/append x.
3. Factoring 1 or 0
Undefined domain for this tutorial.
→ Require n >= 2.
4. Mixing In Floating-Point Division
Casting to
doublecan leave non-integers and break later checks.→ Keep
xandiasint/longso/=is integer division.5. Unnecessary is_prime
Extra prime tests slow and complicate the code.
→ Rely on ordered peeling.
Edge Cases
Handle these before claiming factorization is complete.
n < 2
Reject
0, 1, and negatives are out of scope.
Prime n
Single factor
Output is just n itself (e.g. 17).
Powers of 2
Repeated peels
Inner while must run many times.
56
Classic yes
2 2 2 7.
360
Mixed primes
2 2 2 3 3 5.
Large prime leftover
Fast path care
Remember if x > 1 after the loop.
Theory
⚖️ Facts Worth Knowing
Handy follow-ups interviewers sometimes ask.
- Fundamental theorem. Every n > 1 has a unique prime factorization (order ignored).
- Why no is_prime. Smaller primes are removed first, so composite i never divides what remains.
- Sqrt bound. Any composite leftover would have a factor <= sqrt(x).
- C++ ints. Prefer
longfor largensoi * idoes not overflow.
Drill
🎯 Practice Problems
Try these variations to lock in the pattern.
1. Factor 56
- Expect 2 2 2 7
- Product-check
2. Factor 17
- Single prime
- Leftover path
3. Factor 360
- 2 2 2 3 3 5
- Match Example 3
4. Reject 1
- Guard n >= 2
- No empty loop tricks
Important
Notes
- Definition: prime factors are primes that multiply to n.
- Loop: for each i, while x % i == 0, emit i and divide.
- Fast path: peel 2s, then odds while i*i <= x, then leftover.
- If factoring many numbers, precomputed primes are faster. Related topics: prime check, composite numbers, and GCD use similar divisor logic.
Quick Takeaway: peel candidate factors completely in ascending order; the product of printed primes is n.
Analysis
⏱️ Time and Space Complexity
| Approach | Time | Extra space |
|---|---|---|
| Naive trial (i <= x) | O(n) worst | O(1) (+ output) |
| Sqrt trial | O(sqrt(n)) | O(1) (+ output) |
| Many queries + sieve | amortized better | depends on bound |
For interview demos, start naive; upgrade to sqrt when asked about speed.
🎉 Conclusion
Prime factorization rewrites n >= 2 as a unique product of primes. Peel candidates with an inner while, upgrade to a sqrt bound when needed, and always handle leftover primes in the fast path.
Practice the three examples above, then continue to checking prime numbers.
Divide out every copy of each i; the remaining primes multiply back to n.
Pro Tips
💡 Best Practices
✅ Do
- Require n >= 2
- Peel each factor completely
- Use integer division
/= - Handle leftover in sqrt version
- Product-check sample cases
❌ Don’t
- Factor 0 or 1 here
- Skip repeated peels
- Forget leftover primes
- Use float division
- Add needless
isPrimecalls
Summary
Key Takeaways
Knowledge Unlocked
Five things to remember about prime factors
Factor n the interview-friendly way.
5
Core concepts 01
Rule
primes of n
Definition 02
Peel
while % i
Loop 03
Fast
i*i <= x
Optimize 04
Domain
n >= 2
Guard 05
Cost
O(√n)
Analysis❓ Frequently Asked Questions
A prime factor is a prime number that divides the given number evenly.
Trying factors in order and dividing repeatedly ensures composite candidates stop dividing after smaller primes are removed.
To capture repeated factors like 2, 2, 2 in 56.
Prime factorization here is defined for n >= 2.
Yes, factors print in non-decreasing order.
It tests fewer candidates by stopping around sqrt(x) and handling leftover prime at the end.
2 × 2 × 2 × 7.
The algorithm prints n itself as the only factor.
If factoring many numbers, precomputed primes are faster.
Did you Know? 🔊
Every integer greater than 1 can be written as a product of primes in exactly one way (ignoring order).
Continue to Prime Number
Learn how to check whether a number is prime in C++.
About the author
8 people found this page helpful