56 Composite
- Factors
- 2, 2, 2, 7
Find Prime Factors in C++
What you’ll learn
- What prime factors are (primes you multiply to rebuild a number).
- A trial division program that prints factors in order, using the same idea as the reference code but with clearer names.
- A faster version that peels off 2, then tests odd divisors only up to roughly the square root.
- A live preview, input guards (so
0does not loop forever), and usual edge cases.
Overview
Take 56. You can split it as 56 = 2 × 28 = 2 × 2 × 14 = 2 × 2 × 2 × 7. The primes that show up are 2 (three times) and 7 (once). This page prints that list: 2 2 2 7. The algorithm tries small divisors in order, strips each as many times as it can, and shrinks what is left until nothing is left to strip.
Two programs
Example 1 is the short double loop (easy to explain). Example 2 is the usual interview upgrade.
Live preview
Type 56, 17 (prime), or 360 before compiling.
Safe inputs
We require n >= 2 so 0 cannot get stuck dividing forever.
Prerequisites
for and while loops, remainder %, and integer division /.
- Rough idea of prime: a whole number > 1 whose only positive divisors are 1 and itself (2, 3, 5, 7, 11…).
#include <iostream>,std::cout, and basic function calls.
What are prime factors?
Prime factors are prime numbers that multiply together to give your starting number. The order we print them is smallest first; repeated primes mean “that prime appears more than once.”
This is not the same lesson as “odd numbers”—the old reference page had a copy-paste heading mistake there. Here we stay on factorization the whole time.
Why trying 2, 3, 4, … still works
When i is composite (say 6), its prime pieces (2 and 3) were already removed from the running value x. So 6 cannot divide x anymore unless you missed an earlier factor—you did not. That is why a plain “does it divide?” test is enough without calling a separate isPrime function in this pattern.
Multiply the printout
If you multiply every printed factor together, you get the original n (for n >= 2). For a prime like 17, the only factor listed is 17.
Quick examples
17 Prime
- Factors
- 17 only
360 Many primes
- Starts with
- 2, 2, 2, 3, 3, 5 …
Live preview
Uses the same fast pattern as Example 2 (twos, then odd trial divisors). Capped so inputs stay responsive in C++ tutorial previews.
Algorithm (trial division)
Goal: print every prime factor of n (with repetition), in non-decreasing order, for integers n >= 2.
Validate n
If n < 2, stop or print a message (no prime factorization in this basic form).
Try divisors in order
Let i run from 2 upward. While the current remainder is divisible by i, print i and divide the remainder by i.
Stop when remainder is 1
In the simple version, the for loop can stop when the remainder reaches 1; the code on this page keeps the reference style i <= x for clarity.
📜 Pseudocode
Pseudocode
procedure displayPrimeFactors(n):
if n < 2:
report invalid / stop
x ← n
for i from 2 while i <= x:
while x mod i = 0:
output i
x ← x / i1
Straightforward trial division
Same structure as the reference program: divides_evenly is just a readable name for “remainder is zero.” We guard n < 2 so 0 never enters an infinite while (x % 2 == 0) loop.
c++
#include <iostream>
int divides_evenly(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;
for (int i = 2; i <= x; ++i) {
while (divides_evenly(x, i)) {
std::cout << i << " ";
x /= i;
}
}
std::cout << "\\n";
}
int main() {
int number = 56;
displayPrimeFactors(number);
return 0;
}Explanation
Start with x = 56. At i = 2, peel three twos (56 → 28 → 14 → 7). Later i = 7 peels the seven. The remainder becomes 1 and the loop finishes.
2
Peel 2, then odd divisors up to √x
After removing all factors of 2, test only odd i. Stop when i × i exceeds the current remainder. If anything is left above 1, it is prime. Same printed line for 56 as Example 1.
c++
#include <iostream>
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;
while (x % 2 == 0) {
std::cout << "2 ";
x /= 2;
}
for (long long i = 3; i * i <= x; i += 2) {
while (x % (int)i == 0) {
std::cout << static_cast<int>(i) << " ";
x /= (int)i;
}
}
if (x > 1) {
std::cout << x << " ";
}
std::cout << "\\n";
}
int main() {
int number = 56;
displayPrimeFactors(number);
return 0;
}Explanation
long long i avoids overflow when i * i is formed. The final if (x > 1) catches one large prime left over (for example after trial division on a semiprime).
Notes
Wheel / sieve. For many queries, sieves or precomputed primes beat naive trial division; for one interview number, Example 2 is usually enough.
Types. If n approaches INT_MAX, consider long long for intermediate divisions so you never multiply two big ints by mistake.
Related: prime check, composite numbers, and GCD build on the same divisor ideas.
❓ FAQ
A prime factor is a prime number that divides your target evenly. Breaking a number into prime factors means writing it as primes multiplied together. Example: 56 = 2 × 2 × 2 × 7.
The old name isPrimeFactor sounded like a prime test, but the code only checks divisibility (remainder zero). The magic is the order: you try 2, then 3, then 4… By the time you reach a composite like 4, you already removed all factors of 2, so 4 cannot divide what is left.
A prime can appear more than once (like three 2s in 56). The inner while keeps stripping the same prime until it no longer divides.
Prime factorization is usually defined for integers n >= 2. The programs on this page guard n < 2 so you do not get empty lists or infinite loops on bad input.
Yes. Trying i = 2, 3, 4, … prints factors in non-decreasing order. (Duplicates mean repeated primes.)
Once only odd candidates remain, you can stop testing past sqrt(x) for the current remainder; anything left bigger than 1 is itself a prime factor.
🔄 Input / output examples
Change number in main or read with std::cin >> number;.
n | Printed factors (conceptually) |
|---|---|
| 56 | 2 2 2 7 |
| 17 | 17 |
| 12 | 2 2 3 |
| 1 | Error line from guard (no factorization) |
Edge cases
The reference code did not guard small values; these fixes keep homework answers safe.
n = 0Infinite loop risk
Naive while (x % 2 == 0) on x = 0 never progresses. Always reject n < 2 first.
n = 1Empty product
Standard factorization starts at n >= 2. Say so in the message you print.
Squares
Repeated primes
36 prints 2 2 3 3—duplicates are expected.
⏱️ Time and space complexity
| Version | Time (single n) | Extra space |
|---|---|---|
Example 1 (try every i up to current x) | worst case about O(n) when n is prime | O(1) |
| Example 2 (√ bound) | O(√n) trial divisions typical story | O(1) |
Summary
- Idea: strip smallest divisors first; what you print are prime factors in order.
- Code: guard
n < 2;for+ innerwhile(Example 1) or 2 + odds + leftover (Example 2). - Fixes vs naive reference: correct topic heading, honest helper name, no infinite loop on
0.
Did you know?
The fundamental theorem of arithmetic says: every integer greater than 1 can be written as a product of primes in exactly one way if you ignore order. That is why “listing prime factors” feels so tidy—you are reading off that unique recipe.
About the author
8 people found this page helpful