Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Sieve-Based Prime Factorization

HARDProblemSolveExternal Links

Description

Given a positive integer N, find all prime factors of N and return them in non-decreasing order.

A prime factor is a prime number that divides N exactly. If a prime number divides N multiple times, include it that many times in the result.

For example, the prime factorization of 12 is 2 × 2 × 3, so the result is [2, 2, 3].

Complete the function findPrimeFactors() that takes a positive integer N as input and returns a vector/list of all its prime factors in sorted order. You must implement an efficient solution using the concept of the Sieve of Eratosthenes for precomputation.

Examples

Example 1

Input: N = 12246

Output: 2 3 13 157

Explanation: The prime factorization of 12246 is 2 × 3 × 13 × 157. Each prime factor is unique in this case (no repeated factors). We return all prime factors in ascending order: [2, 3, 13, 157].

Example 2

Input: N = 12

Output: 2 2 3

Explanation: 12 = 2 × 2 × 3 = 2² × 3. The factor 2 appears twice because 12 is divisible by 2 twice (12 → 6 → 3). We include each prime factor as many times as it divides N: [2, 2, 3].

Example 3

Input: N = 13

Output: 13

Explanation: 13 is itself a prime number. Its only prime factor is 13 itself. The result is [13].

Constraints

  • 2 ≤ N ≤ 2 × 10^5

Editorial

Brute Force - Trial Division

Intuition

The most natural way to find prime factors is trial division: try dividing N by every candidate starting from 2. If a candidate divides N, it's a prime factor — extract it completely (divide out all its copies) before moving on.

Why does this produce only prime factors? Because we test candidates in ascending order. When we reach candidate i, all prime factors smaller than i have already been completely extracted. So if i divides the current N, it cannot be composite (its own prime factors would have already been removed). Therefore, every divisor we find is guaranteed to be prime.

Key optimization: We only need to check candidates up to √N. If after checking all candidates up to √N no divisor is found, then N itself must be prime (because any composite number must have at least one factor ≤ √N). If N > 1 after the loop, it's the remaining prime factor.

For example, to factorize 60:

  • Divide by 2 twice: 60 → 30 → 15
  • Divide by 3 once: 15 → 5
  • Now 4² = 16 > 5, so the loop exits. Since 5 > 1, add 5.
  • Result: [2, 2, 3, 5]

Step-by-Step Explanation

Let's trace through N = 12246:

Step 1: Start with N = 12246. Initialize an empty factors list. We will check candidates from i = 2 up to √12246 ≈ 110.7.

Step 2: Try i = 2. Check: 12246 mod 2 = 0 — divisible! Divide: 12246 ÷ 2 = 6123. Check again: 6123 mod 2 ≠ 0. Done with 2. factors = [2]. N = 6123.

Step 3: Try i = 3. Check: 6123 mod 3 = 0 — divisible! (6+1+2+3 = 12, which is divisible by 3). Divide: 6123 ÷ 3 = 2041. Check again: 2041 mod 3 ≠ 0. factors = [2, 3]. N = 2041.

Step 4: Try i = 4 through 12. None of these divide 2041. We skip through them all.

Step 5: Try i = 13. Check: 2041 mod 13 = 0 — divisible! (2041 = 13 × 157). Divide: 2041 ÷ 13 = 157. Check again: 157 mod 13 ≠ 0. factors = [2, 3, 13]. N = 157.

Step 6: Try i = 14. Check loop condition: 14² = 196 > 157. Loop exits! We've checked all candidates up to √157.

Step 7: N = 157 > 1, so 157 must be prime (no factor ≤ √157 ≈ 12.5 was found). Add it. factors = [2, 3, 13, 157].

Result: 12246 = 2 × 3 × 13 × 157. We checked candidates from 2 to 13 — only about 12 iterations.

Trial Division: Factorize N = 60 — Watch trial division check candidate divisors from 2 to √60, extracting prime factors when found, and stopping early when the remaining N must be prime.

Algorithm

  1. Initialize an empty list factors
  2. For each candidate i from 2 while i * i ≤ N:
    • While N is divisible by i:
      • Append i to factors
      • Divide N by i
    • Increment i
  3. If N > 1 after the loop, append N to factors (it's the remaining prime factor)
  4. Return factors

Code

#include <vector>
using namespace std;

class Solution {
public:
    vector<int> findPrimeFactors(int N) {
        vector<int> factors;
        
        for (int i = 2; (long long)i * i <= N; i++) {
            while (N % i == 0) {
                factors.push_back(i);
                N /= i;
            }
        }
        
        // If N > 1, then it's the remaining prime factor
        if (N > 1) {
            factors.push_back(N);
        }
        
        return factors;
    }
};
class Solution:
    def findPrimeFactors(self, N: int) -> list:
        factors = []
        
        i = 2
        while i * i <= N:
            while N % i == 0:
                factors.append(i)
                N //= i
            i += 1
        
        # If N > 1, then it's the remaining prime factor
        if N > 1:
            factors.append(N)
        
        return factors
import java.util.ArrayList;

class Solution {
    ArrayList<Integer> findPrimeFactors(int N) {
        ArrayList<Integer> factors = new ArrayList<>();
        
        for (int i = 2; (long) i * i <= N; i++) {
            while (N % i == 0) {
                factors.add(i);
                N /= i;
            }
        }
        
        // If N > 1, then it's the remaining prime factor
        if (N > 1) {
            factors.add(N);
        }
        
        return factors;
    }
}

Complexity Analysis

Time Complexity: O(√N)

The outer loop runs from i = 2 up to √N. For each candidate, the inner while loop divides N by i, reducing N. In the worst case (N is prime), we iterate through all candidates from 2 to √N without finding any divisor — approximately √N iterations. When N has small factors, the loop exits earlier because N shrinks rapidly.

Space Complexity: O(log N)

The only extra space is the factors list. A number N can have at most log₂(N) prime factors (the worst case being N = 2^k). For N ≤ 2 × 10^5, this is at most 17 factors. Excluding the output, the space is O(1).

Why This Approach Is Not Efficient

Trial division is simple and works well for a single query — O(√N) for N ≤ 2 × 10^5 means at most ~450 operations. But it has fundamental limitations:

1. No precomputed knowledge: Trial division discovers prime factors from scratch every time. It doesn't leverage the fact that the relationship between numbers and their prime factors can be computed once and reused.

2. Redundant work for multiple queries: If we need to factorize Q different numbers, trial division requires O(Q × √N) total work. Each query independently re-discovers which primes divide its input — the same divisibility checks are repeated across queries.

3. The problem specifically requires the Sieve concept: The expected time complexity is O(N log(log N)), which is the signature complexity of the Sieve of Eratosthenes. This hints at a fundamentally different strategy: precompute information about ALL numbers up to N in one pass, then use that precomputed data to factorize instantly.

The Sieve insight: By modifying the Sieve of Eratosthenes to store the Smallest Prime Factor (SPF) for every number up to N, we can:

  • Build the sieve in O(N log log N) time and O(N) space
  • Factorize ANY number in [2, N] in just O(log N) time by following the SPF chain
  • For Q queries: total O(N log log N + Q × log N) — dramatically better when Q is large

Key takeaway: Precomputation transforms a per-query O(√N) problem into a per-query O(log N) problem. This is the power of the sieve-based approach.

Optimal Approach - Smallest Prime Factor (SPF) Sieve

Intuition

The core idea is a two-phase strategy:

Phase 1 — Precompute the SPF Array: Build an array spf[] where spf[i] stores the smallest prime factor of i. This uses a modified Sieve of Eratosthenes.

In the classic sieve, we mark composites as "not prime." Here, instead of just marking, we record which prime first marked each composite. When prime p marks composite j = p × k, we set spf[j] = p — but only if j hasn't already been marked by a smaller prime.

How it works:

  1. Initialize spf[i] = i for all i (assume every number is its own smallest prime factor, i.e., assume it's prime)
  2. For each i from 2 to √N:
    • If spf[i] == i, then i is prime (no smaller prime marked it)
    • For each multiple j = i², i²+i, i²+2i, ... up to N:
      • If spf[j] == j (not yet marked), set spf[j] = i

After the sieve, every composite has its correct smallest prime factor, and primes have spf[p] = p.

Phase 2 — Factorize Using SPF: To find all prime factors of N:

  1. Look up spf[N] — this is the smallest prime factor. Record it.
  2. Divide: N = N / spf[N]
  3. Repeat until N = 1.

Each step removes one prime factor and divides N by at least 2, so factorization takes at most O(log N) steps. Each step is an O(1) array lookup — no divisibility testing needed!

Example: SPF array tells us spf[12] = 2. Then: 12 → spf[12]=2, 12/2=6 → spf[6]=2, 6/2=3 → spf[3]=3, 3/3=1. Result: [2, 2, 3].

Step-by-Step Explanation

Phase 1: SPF Sieve Construction (for range 2 to 15)

Step 1: Initialize spf[i] = i for all i from 2 to 15. Each number starts as its own smallest prime factor (assumed prime).

spf = [_, _, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

Step 2: Process i = 2. Since spf[2] = 2 (equals itself), 2 is prime. Mark all multiples of 2 starting from 2² = 4: set spf[4]=2, spf[6]=2, spf[8]=2, spf[10]=2, spf[12]=2, spf[14]=2.

Step 3: Process i = 3. Since spf[3] = 3 (equals itself), 3 is prime. Mark multiples from 3² = 9: set spf[9]=3. Skip spf[12] (already 2 < 3). Set spf[15]=3.

Step 4: Process i = 4. Since 4² = 16 > 15, the outer loop ends. Sieve construction complete.

Final SPF: [2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3] for indices 2-15.
Primes (spf[i]=i): {2, 3, 5, 7, 11, 13}

Phase 2: Factorize N = 12246 using SPF

Step 5: Look up spf[12246] = 2 (12246 is even). Record factor 2. N = 12246 / 2 = 6123.

Step 6: Look up spf[6123] = 3 (6123 = 3 × 2041). Record factor 3. N = 6123 / 3 = 2041.

Step 7: Look up spf[2041] = 13 (2041 = 13 × 157). Record factor 13. N = 2041 / 13 = 157.

Step 8: Look up spf[157] = 157 (prime — equals itself). Record factor 157. N = 157 / 157 = 1.

Step 9: N = 1, factorization complete. factors = [2, 3, 13, 157]. Only 4 array lookups!

SPF Sieve Construction: Building the Lookup Table (range 2-15) — Watch the modified Sieve of Eratosthenes build the Smallest Prime Factor array. Each prime marks its multiples with itself as their SPF — but only if no smaller prime has already marked them.

SPF Factorization: Extract Prime Factors of N = 12 in O(log N) — Using the precomputed SPF array, factorize 12 by repeatedly looking up the smallest prime factor and dividing — just 3 O(1) lookups instead of trial division.

Algorithm

Phase 1: Build SPF Sieve

  1. Create array spf[0..N]
  2. Initialize spf[i] = i for all i from 2 to N
  3. For each i from 2 while i * i ≤ N:
    • If spf[i] == i (i is prime):
      • For each j = i*i, i*i+i, i*i+2i, ... up to N:
        • If spf[j] == j (not yet marked):
          • Set spf[j] = i

Phase 2: Factorize Using SPF
4. Initialize empty list factors
5. While N > 1:

  • Append spf[N] to factors
  • Set N = N / spf[N]
  1. Return factors

Code

#include <vector>
using namespace std;

class Solution {
public:
    vector<int> findPrimeFactors(int N) {
        // Phase 1: Build Smallest Prime Factor (SPF) sieve
        vector<int> spf(N + 1);
        for (int i = 2; i <= N; i++) spf[i] = i;
        
        for (int i = 2; (long long)i * i <= N; i++) {
            if (spf[i] == i) { // i is prime
                for (int j = i * i; j <= N; j += i) {
                    if (spf[j] == j) { // not yet marked
                        spf[j] = i;
                    }
                }
            }
        }
        
        // Phase 2: Factorize using SPF array
        vector<int> factors;
        int n = N;
        while (n > 1) {
            factors.push_back(spf[n]);
            n /= spf[n];
        }
        
        return factors;
    }
};
class Solution:
    def findPrimeFactors(self, N: int) -> list:
        # Phase 1: Build Smallest Prime Factor (SPF) sieve
        spf = list(range(N + 1))  # spf[i] = i initially
        
        i = 2
        while i * i <= N:
            if spf[i] == i:  # i is prime
                for j in range(i * i, N + 1, i):
                    if spf[j] == j:  # not yet marked
                        spf[j] = i
            i += 1
        
        # Phase 2: Factorize using SPF array
        factors = []
        n = N
        while n > 1:
            factors.append(spf[n])
            n //= spf[n]
        
        return factors
import java.util.ArrayList;

class Solution {
    ArrayList<Integer> findPrimeFactors(int N) {
        // Phase 1: Build Smallest Prime Factor (SPF) sieve
        int[] spf = new int[N + 1];
        for (int i = 2; i <= N; i++) spf[i] = i;
        
        for (int i = 2; (long) i * i <= N; i++) {
            if (spf[i] == i) { // i is prime
                for (int j = i * i; j <= N; j += i) {
                    if (spf[j] == j) { // not yet marked
                        spf[j] = i;
                    }
                }
            }
        }
        
        // Phase 2: Factorize using SPF array
        ArrayList<Integer> factors = new ArrayList<>();
        int n = N;
        while (n > 1) {
            factors.add(spf[n]);
            n /= spf[n];
        }
        
        return factors;
    }
}

Complexity Analysis

Time Complexity: O(N log(log N))

The SPF sieve construction dominates the time. The inner loop for each prime p marks N/p multiples. Summing over all primes: ∑(N/p) for primes p ≤ √N, which is O(N log log N) by Mertens' theorem — the same complexity as the classic Sieve of Eratosthenes.

The factorization phase takes O(log N) per query because each division reduces N by at least half (the smallest prime factor is at least 2, so N is at most halved each step). For N ≤ 2 × 10^5, this is at most 17 steps.

Space Complexity: O(N)

The SPF array requires N + 1 integers. For N = 2 × 10^5, this is about 800 KB — well within memory limits. The factors list requires at most O(log N) space.

Comparison with Trial Division:

MetricTrial DivisionSPF Sieve
PreprocessingNoneO(N log log N)
Per-query timeO(√N)O(log N)
Q queries totalO(Q × √N)O(N log log N + Q × log N)
SpaceO(1)O(N)
For N = 200000~447 ops/query~17 ops/query after sieve