Topics › Bit Manipulation › Advanced Maths

Prime factorisation of a Number

Hard TUF ID 652 A2Z

Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

You are given a positive integer n. Return its prime factorisation as a list of primes with multiplicity, in non-decreasing order, so that the product of the list is n. For example 60 = 2 × 2 × 3 × 5. The factorisation of 1 is the empty list. In the harder version you are asked to factorise many numbers, which is where a sieve of smallest prime factors pays off.

Constraints: 1 ≤ n ≤ 2^31 - 1 for a single number; for the batched version, 1 ≤ n ≤ 10^6 and up to 10^5 numbers.

Example 1

n = 60
answer = [2, 2, 3, 5]

Example 2

n = 12246
answer = [2, 3, 13, 157]

Example 3

n = 1024
answer = [2, 2, 2, 2, 2, 2, 2, 2, 2, 2]     // 2^10

Approach 1: Brute force

Intuition. Try divisors in increasing order starting at 2. Whenever d divides the current n, record d and divide it out, repeating until it no longer divides. Because every smaller prime has already been removed, any d that divides n must be prime, so there is no need for a separate primality test. The weakness is the stopping rule: the loop runs d all the way up to n, which for a prime n means n iterations.

Algorithm.

1. For d from 2 to n (the current n):
2. While n % d == 0, append d and set n = n / d.
3. Return the list.

static List<Integer> bruteForce(int n) {
    List<Integer> factors = new ArrayList<>();
    for (int d = 2; d <= n; d++) {
        while (n % d == 0) {
            factors.add(d);
            n /= d;
        }
    }
    return factors;
}

Complexity. Time O(n) in the worst case (n prime); the divisions themselves total at most log2(n). Space O(log n) for the output.

Why does a composite d never pass n % d == 0? By the time the loop reaches a composite c, every prime factor of c is less than c and has been divided out completely, so n shares no factor with c.

Approach 2: Better, trial division to sqrt(n)

Intuition. Keep the same loop but stop as soon as d × d > n, where n is the current shrinking value. At that point any remaining n > 1 must be prime: if it were composite it would have a factor at most sqrt(n), and all numbers up to sqrt(n) have already been tried and divided out. So the leftover is appended as the last (largest) factor. This single change turns O(n) into O(sqrt(n)), and because n shrinks every time a factor is found, typical inputs finish far faster.

Algorithm.

1. For d from 2 while d × d ≤ n:
2. While n % d == 0, append d and divide n by d.
3. If n > 1 after the loop, append n.

static List<Integer> better(int n) {
    List<Integer> factors = new ArrayList<>();
    for (long d = 2; d * d <= n; d++) {
        while (n % d == 0) {
            factors.add((int) d);
            n /= d;
        }
    }
    if (n > 1) factors.add(n);
    return factors;
}

Complexity. Time O(sqrt(n)), at most about 46340 iterations for any int. Space O(log n) for the output.

The loop variable is a long so that d × d cannot overflow when n is close to 2^31 - 1; with an int, 46341 × 46341 wraps to a negative number and the loop condition becomes meaningless. n /= d with a long divisor compiles because compound assignment casts the result back to int.

For a single number this is the right tool, and it is the method that handles the full int range. Its per-number cost, though, is sqrt(n), and factorising 10^5 numbers up to 10^6 would cost around 10^8 divisions. For many queries, precompute.

Approach 3: Optimal, sieve of smallest prime factors

Intuition. Factorising by trial division is slow because the loop does not know where the next factor is. Give it a lookup table instead: spf[x], the smallest prime factor of x, for every x up to the limit. Then factorising n is a chain of table reads: p = spf[n] is the first factor; divide, read spf of the quotient, and so on until n becomes 1. Every step removes at least a factor of 2, so a query takes at most log2(n) steps and no divisions beyond the obvious one.

The table is built like the sieve of Eratosthenes. Process i from 2 upwards; if spf[i] is still 0, then i is prime, so set spf[i] = i and walk its multiples from i × i, setting spf[j] = i for every j that has not been assigned yet. Because primes are processed in increasing order, the first prime to reach j is its smallest prime factor, and the “not yet assigned” check keeps a larger prime from overwriting it. Multiples below i × i already have a smaller prime factor and were assigned earlier.

Algorithm.

Precomputation:

1. Allocate spf[0..limit] filled with 0.
2. For i from 2 to limit: if spf[i] == 0, set spf[i] = i and for j = i × i, i × i + i, ... up to limit, set spf[j] = i if spf[j] is still 0.

Per query:

1. While n > 1: let p = spf[n], append p, set n = n / p.

static int[] smallestPrimeFactors(int limit) {
    int[] spf = new int[limit + 1];
    for (int i = 2; i <= limit; i++) {
        if (spf[i] == 0) {                                // i is prime
            spf[i] = i;
            for (long j = (long) i * i; j <= limit; j += i) {
                if (spf[(int) j] == 0) spf[(int) j] = i;  // first prime to reach j is its smallest factor
            }
        }
    }
    return spf;
}

static List<Integer> optimal(int n, int[] spf) {
    List<Integer> factors = new ArrayList<>();
    while (n > 1) {
        int p = spf[n];
        factors.add(p);
        n /= p;
    }
    return factors;
}

Dry run. The table up to 12 is

Factorising n = 60 with a table that extends to 60:

Result [2, 2, 3, 5], produced in non-decreasing order automatically, because each step removes the smallest remaining prime.

Complexity. Precomputation O(limit log log limit) time and O(limit) space (an int[] of 10^6 is 4 MB). Each query O(log n) time. For 10^5 queries up to 10^6, total work is a few million operations, versus roughly 10^8 for repeated trial division.

Why is the output sorted? spf[n] is the smallest prime dividing the current n, and dividing by it can only remove copies of that prime, so the next smallest prime factor is at least as large.

Edge cases and pitfalls

• n = 1. All three methods return an empty list; the while (n > 1) and d × d ≤ n conditions fail immediately. Check that the product of an empty list, 1, equals n.
• n prime. Trial division finds nothing and appends the leftover n. The table has spf[n] = n, so one step suffices. 999983 is the largest prime below 10^6 and 2147483647 the largest int; both are tested.
• Prime powers. 1024 must give ten 2s, so the inner while (not an if) is essential in Approaches 1 and 2; in Approach 3 the repetition happens naturally across iterations.
• Overflow. d × d and i × i are computed in long. Also the product of the returned factors should be verified in long if you check it, since intermediate products equal n only at the end.
• Table range. optimal indexes spf[n], so n must not exceed the table’s limit. For a single n far beyond any reasonable table (such as 10^9), use Approach 2; the sieve is for many bounded queries.
• Marking from i × i. With limit = 10^6, i × i exceeds the limit once i > 1000, so the inner loop simply does not run for large primes; the (long) cast prevents the product from overflowing before the comparison.
• Distinct versus with multiplicity. This problem wants multiplicity. If you need distinct primes only, strip all copies of each factor before recording the next one, or de-duplicate the output.

Related problems

• Print Prime Factors of a Number is the distinct-primes version of the same trial division.
• Count primes in range L to R builds the same sieve as a boolean array and adds prefix sums.
• Divisors of a Number uses the exponents from this factorisation to count divisors as the product of (e + 1).
• Check for Prime Number is the one-number special case where the factorisation has a single entry.
• GCD of Two Numbers can be computed from two factorisations by taking minimum exponents, although Euclid’s algorithm is far faster in practice.