Find Largest Prime Factor in Java
Problem
The largest prime factor of a number is the biggest prime that divides it evenly, found by stripping away every smaller prime factor first.
Given a number, find its largest prime factor.
Java Program
public class LargestPrimeFactor {
public static void main(String[] args) {
int n = 780;
int largest = -1;
for (int i = 2; (long) i * i <= n; i++) {
while (n % i == 0) {
largest = i; // record i as the largest factor found so far
n /= i; // strip this factor out before trying the next candidate
}
}
if (n > 1) largest = n; // whatever remains is itself prime
System.out.println("Largest prime factor: " + largest);
}
}Output
Core Logic
Repeatedly dividing out every factor of each candidate divisor, from smallest to largest, strips the number down to nothing but its largest prime factor by the time the loop ends.
- 1The loop tries every candidate divisor
istarting from2, only whilei * i <= n. - 2The inner
while (n % i == 0)keeps dividingiout ofnfor as long as it evenly divides, recordingias the largest factor found so far each time. - 3Once
ino longer dividesn, the outer loop moves to the next candidate. - 4If anything greater than
1remains after the loop, that remainder is itself prime and becomes the final answer.
780, dividing out 2 twice leaves 195, dividing out 3 leaves 65, dividing out 5 leaves 13 — and since 13 * 13 > 13, the loop stops and the remaining 13 is reported as the largest prime factor.Key Point: The loop only ever needs to reach √n relative to the *shrinking* value of n, not the original — once every smaller factor is divided out, whatever's left is guaranteed to be prime.
Why: The loop only needs to try divisors up to √n, since any factor larger than that must pair with one already found, and only the running largest value is kept.
Key Concepts
Approach 2: Handle 2 Separately (Odd-Only Loop)
public class LargestPrimeFactorOddOnly {
public static void main(String[] args) {
int n = 780;
int largest = -1;
while (n % 2 == 0) {
largest = 2;
n /= 2;
}
// Only odd candidates remain possible once every factor of 2 is gone
for (int i = 3; (long) i * i <= n; i += 2) {
while (n % i == 0) {
largest = i;
n /= i;
}
}
if (n > 1) largest = n;
System.out.println("Largest prime factor: " + largest);
}
}
Output
Core Logic
Dividing out every factor of 2 up front means the main loop never has to waste time testing even candidates again — it can skip straight to odd numbers.
- 1A
while (n % 2 == 0)loop strips out every factor of 2 before anything else runs. - 2The main loop then starts at
3and increments by2each time, trying only odd candidates. - 3The same inner
whiledivision logic applies for each odd candidate. - 4As before, whatever remains greater than
1after the loop is the final largest factor.
780, dividing out 2 twice up front leaves 195; the odd-only loop then finds 3 and 5, leaving 13 as the remaining largest factor.Key Point: Since every even number past 2 can never be prime, testing them in the main loop was always wasted work — this cuts the number of candidates tried roughly in half.
Why: Handling factor 2 up front lets the main loop skip every even candidate divisor, roughly halving the number of iterations tried, though the asymptotic bound is unchanged.