☕ DSA Java Articles

Topics › Bit Manipulation › Advanced Maths

Print Prime Factors of a Number

Hard TUF ID 2853 A2Z

Java source ↗ Edit this article ↗

Problem

You are given a positive integer n. Return its distinct prime factors in increasing order. A prime factor is a prime p with n % p == 0; each prime is listed once no matter how many times it divides n. The number 1 has no prime factors, and a prime number is its own only prime factor.

Constraints: 1 ≤ n ≤ 2^31 - 1. The number of distinct prime factors of any int is at most 9 (since 2 × 3 × 5 × 7 × 11 × 13 × 17 × 19 × 23 × 29 already exceeds 2^31), so the output is tiny; the whole cost is in finding the factors.

Example 1

n = 60
answer = [2, 3, 5]        // 60 = 2^2 * 3 * 5; the repeated 2 is listed once

Example 2

n = 97
answer = [97]             // 97 is prime

Example 3

n = 1
answer = []               // 1 has no prime factors

Approach 1: Brute force

Intuition. A prime factor is a number that (a) divides n and (b) is prime. Test every candidate from 2 to n for both conditions. The divisibility test is one modulo; the primality test is a trial division loop up to sqrt(candidate). Correct, but it visits every integer up to n even though almost none of them divide n.

Algorithm.

  1. For i from 2 to n:
  2. If n % i == 0 and isPrime(i), add i to the result.
  3. Return the result (already increasing because i increases).
static List<Integer> bruteForce(int n) {
    List<Integer> factors = new ArrayList<>();
    for (int i = 2; i <= n; i++) {
        if (n % i == 0 && isPrime(i)) factors.add(i);
    }
    return factors;
}

static boolean isPrime(int x) {
    if (x < 2) return false;
    for (long d = 2; d * d <= x; d++) {
        if (x % d == 0) return false;
    }
    return true;
}

Complexity. Time O(n × sqrt(n)) in the worst case, although the short-circuit && means isPrime only runs for actual divisors, so in practice it is O(n + k × sqrt(n)) for k divisors. Either way the O(n) scan dominates and is hopeless for n near 2 × 10^9. Space O(1) beyond the output.

Approach 2: Better, scan only to sqrt(n)

Intuition. Divisors come in pairs: if d divides n then so does n / d, and one of the two is at most sqrt(n). So scanning d from 2 to sqrt(n) discovers every divisor, either directly or as a partner. Run the primality test on each divisor found and keep the primes. If no divisor at all is found, n itself is prime.

Algorithm.

  1. For d from 2 while d × d ≤ n:
  2. If n % d == 0: add d if it is prime; let other = n / d; if other != d and other is prime, add it too.
  3. If nothing was added and n ≥ 2, add n (it is prime).
  4. Sort, because partners arrive in decreasing order mixed with the increasing d.
static List<Integer> better(int n) {
    List<Integer> factors = new ArrayList<>();
    for (long d = 2; d * d <= n; d++) {
        if (n % d == 0) {
            if (isPrime((int) d)) factors.add((int) d);
            int other = (int) (n / d);
            if (other != d && isPrime(other)) factors.add(other);
        }
    }
    if (factors.isEmpty() && n >= 2) factors.add(n);   // no divisor up to sqrt(n): n itself is prime
    Collections.sort(factors);
    return factors;
}

Complexity. Time O(sqrt(n) + k × sqrt(n)), where k is the number of divisors (at most 1600 for an int, usually far fewer). Space O(k) for the candidate list.

Why no duplicates? A prime p ≤ sqrt(n) is added when d = p; it could only be added again as a partner n / d = p, which needs d = n / p ≥ sqrt(n), and then d == other, which is skipped. A prime p > sqrt(n) is never a value of d, and it is the partner of exactly one d, namely n / p.

Why “no divisor found implies prime”? Every composite n has a factor in [2, sqrt(n)]: if n = a × b with both a, b > sqrt(n), then a × b > n, a contradiction.

Approach 3: Optimal, divide out each factor

Intuition. The primality tests in Approach 2 are redundant work. Make the loop itself guarantee primality: whenever d divides the current n, record d and then divide n by d as many times as possible. After that, n contains no factor d. Then by induction, when the loop reaches a composite value c, every prime factor of c is smaller than c and has already been stripped out of n, so c cannot divide n. The only values of d that ever pass the n % d == 0 test are primes, with no explicit test. Shrinking n also shrinks the loop bound d × d ≤ n, so the scan usually stops long before sqrt of the original number.

Algorithm.

  1. For d from 2 while d × d ≤ n (the current, shrinking n):
  2. If n % d == 0, add d to the result and repeat n /= d until d no longer divides n.
  3. After the loop, if n > 1, the remaining n is a prime larger than sqrt of the original; add it.
static List<Integer> optimal(int n) {
    List<Integer> factors = new ArrayList<>();
    for (long d = 2; d * d <= n; d++) {
        if (n % d == 0) {
            factors.add((int) d);
            while (n % d == 0) n /= d;      // strip every copy of d
        }
    }
    if (n > 1) factors.add(n);              // the leftover is one prime larger than sqrt(original n)
    return factors;
}

Dry run on n = 60:

d d × d ≤ n? n % d == 0? action n after factors
2 4 ≤ 60 yes add 2, strip 2 twice 15 [2]
3 9 ≤ 15 yes add 3, strip once 5 [2, 3]
4 16 ≤ 5 no, loop ends   5 [2, 3]
end     n = 5 > 1, add it   [2, 3, 5]

The output is already sorted because d increases and the leftover prime is larger than every d tried.

Complexity. Time O(sqrt(n)): the loop runs at most sqrt(n) iterations, and the total number of divisions across all while loops is at most log2(n), since each division at least halves n. Space O(1) beyond the output.

Why can there be at most one leftover prime? If two primes p, q > sqrt(original n) both divided n, then p × q > n. So after stripping all small primes, what remains is 1 or a single prime.

Edge cases and pitfalls