Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Prime Factorization

HARDProblemSolveExternal Links

Description

Given a positive integer n, find all the prime factors of n and return them in a list (with repetitions, in non-decreasing order).

A prime factor is a factor that is a prime number. The prime factorization of a number is the representation of that number as a product of its prime factors.

For example, 18 = 2 × 3 × 3, so the prime factors of 18 are [2, 3, 3].

By the Fundamental Theorem of Arithmetic, every integer greater than 1 either is a prime itself or can be represented as a unique product of prime numbers (up to the order of the factors).

Examples

Example 1

Input: n = 18

Output: [2, 3, 3]

Explanation: 18 = 2 × 3 × 3. We first divide by 2 (18/2 = 9), then by 3 twice (9/3 = 3, 3/3 = 1). The prime factors are 2, 3, and 3.

Example 2

Input: n = 25

Output: [5, 5]

Explanation: 25 = 5 × 5. The only prime factor is 5, appearing twice.

Example 3

Input: n = 84

Output: [2, 2, 3, 7]

Explanation: 84 = 2 × 2 × 3 × 7. We divide by 2 twice (84→42→21), then by 3 once (21→7), and 7 is prime. The prime factors are 2, 2, 3, 7.

Example 4

Input: n = 13

Output: [13]

Explanation: 13 is itself a prime number. It cannot be broken down further. The only prime factor is 13.

Constraints

  • 2 ≤ n ≤ 10^9

Editorial

Brute Force

Intuition

The most direct approach is to try dividing n by every integer starting from 2 up to n itself. For each divisor i, as long as n is divisible by i, we record i as a prime factor and divide n by i. We then move on to the next integer.

Why does this work? Because we try divisors in increasing order. By the time we reach some composite number like 6, all factors of 2 and 3 have already been extracted from n. So n will no longer be divisible by 6 (or any composite number), meaning only prime divisors will actually produce results.

Think of it as peeling layers off an onion — you remove the smallest factor layer by layer. Since composites are built from smaller primes, they can never "match" once their constituent primes have been stripped away.

Step-by-Step Explanation

Let's trace through with n = 84:

Step 1: Start with i = 2. Is 84 divisible by 2? Yes (84 % 2 = 0). Record 2. Divide: n = 84 / 2 = 42.

Step 2: Still i = 2. Is 42 divisible by 2? Yes (42 % 2 = 0). Record 2. Divide: n = 42 / 2 = 21.

Step 3: Still i = 2. Is 21 divisible by 2? No (21 % 2 = 1). Move to i = 3.

Step 4: i = 3. Is 21 divisible by 3? Yes (21 % 3 = 0). Record 3. Divide: n = 21 / 3 = 7.

Step 5: Still i = 3. Is 7 divisible by 3? No (7 % 3 = 1). Move to i = 4.

Step 6: i = 4. Is 7 divisible by 4? No. i = 5? No. i = 6? No. i = 7? Yes (7 % 7 = 0). Record 7. Divide: n = 7 / 7 = 1.

Step 7: n = 1, we are done. The loop continues checking i = 8, 9, ... but n is already 1, so nothing more happens.

Result: Prime factors = [2, 2, 3, 7]. Verify: 2 × 2 × 3 × 7 = 84. ✓

Brute Force — Trial Division from 2 to n — Watch how we try each divisor from 2 upward, repeatedly dividing n by the current divisor until it no longer divides evenly, then moving to the next candidate.

Algorithm

  1. Initialize an empty list factors
  2. For each integer i from 2 to n:
    a. While n is divisible by i (n % i == 0):
    • Append i to factors
    • Divide n by i (n = n / i)
  3. Return factors

Code

#include <vector>
using namespace std;

vector<int> primeFactors(int n) {
    vector<int> factors;
    for (int i = 2; i <= n; i++) {
        while (n % i == 0) {
            factors.push_back(i);
            n = n / i;
        }
    }
    return factors;
}
def prime_factors(n: int) -> list[int]:
    factors = []
    for i in range(2, n + 1):
        while n % i == 0:
            factors.append(i)
            n //= i
    return factors
import java.util.ArrayList;
import java.util.List;

public class Solution {
    public List<Integer> primeFactors(int n) {
        List<Integer> factors = new ArrayList<>();
        for (int i = 2; i <= n; i++) {
            while (n % i == 0) {
                factors.add(i);
                n = n / i;
            }
        }
        return factors;
    }
}

Complexity Analysis

Time Complexity: O(n)

In the worst case, when n is a prime number, the outer loop runs from 2 all the way to n before finding that n itself is a factor. This means we iterate through nearly n values. For n up to 10^9, this is approximately 10^9 iterations — far too slow for most competitive programming time limits.

Space Complexity: O(log n)

The output list holds at most log₂(n) factors, since each prime factor is at least 2, and n can be halved at most log₂(n) times. For n = 10^9, this is at most about 30 factors.

Why This Approach Is Not Efficient

The brute force has two major inefficiencies:

1. It checks composite divisors: After extracting all 2s, we still check 4, 6, 8, ... — but none of these can ever divide n anymore, because the factor of 2 they contain has already been removed. This is wasted work.

2. It scans all the way to n: The worst case occurs when n is a large prime (e.g., 999999937). The loop runs nearly a billion iterations just to discover that n divides itself. But we don't actually need to search that far.

Here's the key mathematical insight: if n has a factor other than 1 and itself, at least one of those factors must be ≤ √n. This is because if both factors were greater than √n, their product would exceed n — a contradiction.

So if we only check divisors up to √n and don't find any, then n itself must be prime — and we can immediately record it as the last factor. This cuts our search space from n down to √n, which for n = 10^9 means checking only ~31,623 values instead of 1,000,000,000.

Additionally, after extracting all factors of 2, every remaining factor must be odd. So we can skip even numbers entirely, halving the work again.

Optimal Approach - Trial Division up to √n

Intuition

The optimal approach exploits the mathematical property that every composite number n has at least one prime factor p ≤ √n. This means we only need to check potential divisors up to √n.

The algorithm works in three phases:

Phase 1 — Extract all 2s: Handle the only even prime separately. While n is even, divide by 2 and record it. After this step, n is guaranteed to be odd.

Phase 2 — Check odd divisors from 3 to √n: Since n is now odd, we only need to check odd divisors (3, 5, 7, 9, 11, ...). For each odd number i, while i divides n, extract it. We stop when i² > n.

Phase 3 — Handle remaining prime: If after all divisions n is still greater than 1, then n itself is a prime factor (it's the one large prime that couldn't be caught by divisors ≤ √n). Record it.

Why is this so much faster? Instead of iterating up to n, we iterate up to √n. For n = 10^9, √n ≈ 31,623. And since we skip even numbers, we effectively check only ~15,811 candidates. This is a reduction from 10^9 operations to about 10^4 — a factor of 100,000× speedup!

Step-by-Step Explanation

Let's trace through with n = 84:

Phase 1 — Extract 2s:

  • 84 % 2 = 0 → record 2, n = 42
  • 42 % 2 = 0 → record 2, n = 21
  • 21 % 2 = 1 → done with 2s. n is now odd (21).

Phase 2 — Odd divisors from 3 to √21 ≈ 4.58:

  • i = 3: 21 % 3 = 0 → record 3, n = 7
  • i = 3: 7 % 3 ≠ 0 → move on
  • i = 5: Check stopping condition: 5² = 25 > 7 → stop loop.

Phase 3 — Remaining prime:

  • n = 7 > 1, so 7 is a prime factor. Record 7.

Result: [2, 2, 3, 7]. Verify: 2 × 2 × 3 × 7 = 84. ✓

Notice we only checked divisors 2, 3, and 5 (where 5 immediately triggered the stop condition). The brute force would have checked 2, 3, 4, 5, 6, 7 — and for larger numbers the savings are dramatically greater.

Let's also trace n = 13 (a prime number):

Phase 1: 13 % 2 ≠ 0 → no 2s.
Phase 2: i = 3: 3² = 9 ≤ 13, but 13 % 3 ≠ 0. Next i = 5: 5² = 25 > 13 → stop.
Phase 3: n = 13 > 1 → record 13.
Result: [13]. Only 2 divisor checks instead of 13.

Optimal Trial Division — Three-Phase Factorization — Watch the three-phase approach: first extract all 2s, then check odd divisors up to √n, and finally handle any remaining large prime. Notice how much less work is done compared to brute force.

Algorithm

  1. Initialize an empty list factors
  2. Phase 1 — Extract 2s: While n is even (n % 2 == 0):
    • Append 2 to factors
    • Divide n by 2
  3. Phase 2 — Odd divisors: For i = 3, 5, 7, ... while i × i ≤ n:
    • While n % i == 0:
      • Append i to factors
      • Divide n by i
    • Increment i by 2
  4. Phase 3 — Remaining prime: If n > 1:
    • Append n to factors (n is a prime factor)
  5. Return factors

Code

#include <vector>
using namespace std;

vector<int> primeFactors(int n) {
    vector<int> factors;

    // Phase 1: Extract all factors of 2
    while (n % 2 == 0) {
        factors.push_back(2);
        n = n / 2;
    }

    // Phase 2: Check odd divisors from 3 to sqrt(n)
    for (int i = 3; (long long)i * i <= n; i += 2) {
        while (n % i == 0) {
            factors.push_back(i);
            n = n / i;
        }
    }

    // Phase 3: If n is still > 1, then it is a prime factor
    if (n > 1) {
        factors.push_back(n);
    }

    return factors;
}
def prime_factors(n: int) -> list[int]:
    factors = []

    # Phase 1: Extract all factors of 2
    while n % 2 == 0:
        factors.append(2)
        n //= 2

    # Phase 2: Check odd divisors from 3 to sqrt(n)
    i = 3
    while i * i <= n:
        while n % i == 0:
            factors.append(i)
            n //= i
        i += 2

    # Phase 3: If n is still > 1, it is a prime factor
    if n > 1:
        factors.append(n)

    return factors
import java.util.ArrayList;
import java.util.List;

public class Solution {
    public List<Integer> primeFactors(int n) {
        List<Integer> factors = new ArrayList<>();

        // Phase 1: Extract all factors of 2
        while (n % 2 == 0) {
            factors.add(2);
            n = n / 2;
        }

        // Phase 2: Check odd divisors from 3 to sqrt(n)
        for (int i = 3; (long) i * i <= n; i += 2) {
            while (n % i == 0) {
                factors.add(i);
                n = n / i;
            }
        }

        // Phase 3: If n is still > 1, it is a prime factor
        if (n > 1) {
            factors.add(n);
        }

        return factors;
    }
}

Complexity Analysis

Time Complexity: O(√n)

Phase 1 runs at most log₂(n) times (each iteration halves n). Phase 2 iterates over odd numbers from 3 to √n, which is at most √n/2 iterations. For each divisor i, the inner while loop runs at most log_i(n) times. The dominant cost is the outer loop of Phase 2: O(√n). For n = 10^9, this is about 31,623 iterations — extremely fast.

Space Complexity: O(log n)

The output list stores at most log₂(n) prime factors (since the smallest prime is 2, and each factor at least halves n). For n = 10^9, this is at most ~30 factors. No additional data structures are needed beyond the output list.