56Composite
- Factors
- 2, 2, 2, 7
Find Prime Factors in Java
What you’ll learn
- What prime factors are and how repeated factors are represented.
- A clear trial division approach and a faster sqrt-based variant.
- How factorization output stays naturally sorted in non-decreasing order.
- A live preview, input guards, and common interview edge cases.
Overview
For 56, the prime factorization is 2 x 2 x 2 x 7. The algorithm tries divisors in increasing order, repeatedly divides out matching factors, and shrinks the number until all prime pieces are printed.
Two Java examples
A simple all-divisors loop and an optimized sqrt-style version.
Live preview
Try 56, 17, or 360 instantly.
Input guard
We enforce n >= 2 for valid prime factorization.
Prerequisites
for/while loops, remainder %, and integer division.
- Prime number basics and factor divisibility checks.
- Reading Java console output and tracing loop states.
What are prime factors?
Prime factors are prime numbers whose product gives the original number. Repetition matters: 12 = 2 x 2 x 3.
Trial division prints factors in sorted order automatically when divisors are tested from small to large.
Why this factor order works
If a small prime factor exists, it appears before larger factors. By dividing it out completely, remaining factors can be found similarly until the number becomes 1 or one leftover prime remains.
Check
Multiplying printed factors reconstructs the original input n.
Quick examples
17Prime
- Factors
- 17 only
360Many
- Starts with
- 2, 2, 2, 3, 3, 5...
Live preview
Uses the optimized approach: remove 2s first, then test odd divisors.
Algorithm (trial division)
Goal: print prime factors of n in non-decreasing order.
Validate input
Reject when n < 2.
Strip factors
Repeatedly divide by each divisor while it divides exactly.
Finish with leftover prime
If remainder is greater than 1, print it as final prime factor.
📜 Pseudocode
Pseudocode
function printPrimeFactors(n):
if n < 2: stop
while n mod 2 == 0:
print 2
n = n / 2
i = 3
while i * i <= n:
while n mod i == 0:
print i
n = n / i
i = i + 2
if n > 1:
print n1
Simple trial division
java
public class Main {
static void printPrimeFactors(int n) {
if (n < 2) {
System.out.println("Enter n >= 2.");
return;
}
System.out.print("Prime factors of " + n + " are: ");
for (int i = 2; i <= n; i++) {
while (n % i == 0) {
System.out.print(i + " ");
n /= i;
}
}
System.out.println();
}
public static void main(String[] args) {
printPrimeFactors(56);
}
}2
Optimized sqrt-style version
java
public class Main {
static void printPrimeFactors(int n) {
if (n < 2) {
System.out.println("Enter n >= 2.");
return;
}
System.out.print("Prime factors of " + n + " are: ");
while (n % 2 == 0) {
System.out.print("2 ");
n /= 2;
}
for (int i = 3; (long) i * i <= n; i += 2) {
while (n % i == 0) {
System.out.print(i + " ");
n /= i;
}
}
if (n > 1) {
System.out.print(n + " ");
}
System.out.println();
}
public static void main(String[] args) {
printPrimeFactors(56);
}
}Optimization notes
After removing factor 2, test only odd divisors up to sqrt(n).
❓ FAQ
A prime factor is a prime number that divides n exactly. Example: 56 = 2 x 2 x 2 x 7.
Because the same prime can repeat many times, so we keep dividing while it still divides.
Prime factorization is usually defined for n >= 2, so this tutorial rejects smaller values.
Yes. Trial division from small to large naturally prints factors in non-decreasing order.
You only test divisors up to sqrt(current remainder), then handle leftover prime > 1.
Typical trial division optimization is about O(sqrt(n)) time and O(1) extra space.
🔄 Input / output examples
| Input | Prime factors |
|---|---|
56 | 2 2 2 7 |
12 | 2 2 3 |
Edge cases
n < 2
Prime factorization is defined for integers 2 and above.
Prime n
A prime like 17 returns itself as the only factor.
⏱️ Time and space complexity
| Version | Time | Extra space |
|---|---|---|
| Simple trial division | up to O(n) | O(1) |
| Optimized sqrt-style | about O(√n) | O(1) |
Summary
- Trial division prints prime factors in sorted order.
- Sqrt-bounded approach improves runtime for larger inputs.
Did you know?
Every integer greater than 1 has a unique prime factorization (ignoring order).
About the author
8 people found this page helpful