Prime Factorization in Java
Problem
Prime factorization expresses a number as a product of primes, each raised to however many times it divides in — every integer greater than 1 has exactly one such factorization.
Given a number, express it as a product of its prime factors, with each factor's exponent shown.
Java Program
public class PrimeFactorization {
public static void main(String[] args) {
int n = 60;
int original = n;
StringBuilder result = new StringBuilder();
for (int i = 2; (long) i * i <= n; i++) {
int power = 0;
while (n % i == 0) {
power++; // count how many times i divides evenly
n /= i;
}
if (power > 0) {
if (result.length() > 0) result.append(" x ");
result.append(i);
if (power > 1) result.append("^").append(power); // only show the exponent when it's more than 1
}
}
if (n > 1) {
if (result.length() > 0) result.append(" x ");
result.append(n); // whatever remains is itself a prime factor
}
System.out.println(original + " = " + result);
}
}Output
Core Logic
Counting how many times each candidate divisor divides evenly before moving to the next one builds the full factorization, exponent and all, in a single pass.
- 1The loop tries every candidate divisor
ifrom2up to√n, wherenshrinks as factors are divided out. - 2For each candidate, an inner
whileloop keeps dividingiout ofnand counts how many times it succeeded intopower. - 3If
poweris greater than zero,iis a factor — it's appended to the result, with a^powersuffix only when the exponent is more than 1. - 4If anything greater than
1remains once the loop ends, that remainder is itself a prime factor with exponent 1, appended at the end.
60, dividing out 2 twice gives power = 2 (shown as 2^2), dividing out 3 once and 5 once each give exponent 1 (shown without a suffix), producing 60 = 2^2 x 3 x 5.Key Point: The exponent suffix is only added when power > 1 — writing every factor as factor^1 would be technically correct but far less readable than just factor.
Why: Trial division only needs to test divisors up to √n, and the result holds at most O(log n) distinct prime factors, since each one at least doubles the value it divides out of.
Key Concepts
Approach 2: Collecting Factors in a List
import java.util.ArrayList;
import java.util.List;
public class PrimeFactorizationList {
public static void main(String[] args) {
int n = 60;
int original = n;
List<Integer> factors = new ArrayList<>();
for (int i = 2; (long) i * i <= n; i++) {
while (n % i == 0) {
factors.add(i); // record this factor once per division
n /= i;
}
}
if (n > 1) factors.add(n);
StringBuilder result = new StringBuilder();
int i = 0;
while (i < factors.size()) {
int factor = factors.get(i);
int power = 0;
while (i < factors.size() && factors.get(i) == factor) { // count consecutive duplicates
power++;
i++;
}
if (result.length() > 0) result.append(" x ");
result.append(factor);
if (power > 1) result.append("^").append(power);
}
System.out.println(original + " = " + result);
}
}
Output
Core Logic
Collecting every prime factor into a flat list first — with duplicates for repeated factors — and grouping them afterward separates 'finding the factors' from 'formatting the output'.
- 1The same trial-division loop divides out each factor, but instead of counting exponents inline, it appends the factor to a
List<Integer>once per division. - 2For
60, this produces the flat list[2, 2, 3, 5]— every factor listed as many times as it divides in. - 3A second pass walks the list, counting how many consecutive entries share the same value to reconstruct each exponent.
- 4The grouped result is formatted the same way as the single-phase version, with a
^powersuffix only when the exponent exceeds 1.
[2, 2, 3, 5] groups into 2 (count 2), 3 (count 1), and 5 (count 1), producing the same 60 = 2^2 x 3 x 5.Key Point: This does strictly more work than counting exponents inline — the trade-off is that the raw factor list is useful on its own if some other part of a program needs the factors without their exponents.
Why: Every prime factor found, with its own multiplicity, is stored in the list before the grouping pass runs, so the list's size is bounded by how many times n can be divided down to 1.