Prime Factorization

This lesson covers prime factorization in Java, so you understand implementing a number-theory algorithm using a loop. It's for anyone searching "Java prime factorization implementation."

Prime factorization expresses a number as a product of prime numbers. Try dividing starting from 2, and if it divides evenly, keep dividing by that same number — that's the procedure.

The example starts with d = 2, and as long as n is divisible by d, adds d to the result with factors.add(d) while dividing with n /= d; once it's no longer divisible, it increments d by 1 — repeating until n becomes 1.

A common early mistake is the nested loop structure. The key to understanding it is the combination of two levels of repetition — the outer loop increasing the divisor d, and the inner loop dividing repeatedly as long as it divides evenly.

This is an important idea spanning both math and computer science, underlying the security of cryptography (like RSA encryption) too. The number 1 divides evenly into everything, so it needs to be excluded from prime factorization.

📖 Reference code

import java.util.*;

public class Main {
    static List<Integer> primeFactors(int n) {
        List<Integer> factors = new ArrayList<>();
        int d = 2;
        while (n > 1) {
            while (n % d == 0) {
                factors.add(d);
                n /= d;
            }
            d++;
        }
        return factors;
    }

    public static void main(String[] args) {
        System.out.println(primeFactors(60));
        System.out.println(primeFactors(97));
    }
}

✍️ Your code

Type your code, then press "Run"

🧪 This site can't compile or run Java directly, so it checks on the spot whether what you typed matches the reference code (scoring happens entirely in your browser — nothing is sent anywhere).