{"title":"Prime Sieve","description":"","content":"Prime numbers appear in many coding interview problems, especially those involving factorization, divisibility, and number theory. A naive approach to checking primes works for small inputs, but quickly becomes too slow when constraints grow.\n\nThe **Prime Sieve** precomputes all primes up to a limit in one pass instead of checking each number independently. The rest of this chapter covers the trial-division primality test, the Sieve of Eratosthenes, and the Smallest Prime Factor (SPF) sieve for fast prime factorization.\n\n---\n\n# What Makes a Number Prime?\n\nA prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. The first few primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.\n\nA few things to note:\n\n- 1 is **not** a prime number (by definition).\n- 2 is the **only** even prime. Every other even number is divisible by 2.\n- If a number n has no divisors up to sqrt(n), it is prime. If `n = a · b` and both `a` and `b` are greater than sqrt(n), then `a · b > n`, which is a contradiction.\n\nThis leads to two fundamentally different approaches: checking one number at a time (trial division) versus generating all primes up to a limit (sieving). The diagram below previews what the sieve does. Every composite is annotated with the smallest prime that crosses it off, while primes stay green.\n\n\n```mermaid\nflowchart LR\n A[\"2\"]:::green --> B[\"3\"]:::green\n B --> C[\"4 = 2·2\"]:::red\n C --> D[\"5\"]:::green\n D --> E[\"6 = 2·3\"]:::red\n E --> F[\"7\"]:::green\n F --> G[\"8 = 2·4\"]:::red\n G --> H[\"9 = 3·3\"]:::orange\n H --> I[\"10 = 2·5\"]:::red\n I --> J[\"11\"]:::green\n J --> K[\"12 = 2·6\"]:::red\n K --> L[\"13\"]:::green\n\n classDef green fill:#69db7c,stroke:#000,color:#000\n classDef red fill:#ff8787,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n```\n\n\nGreen nodes are prime. Red nodes are even composites crossed off when `p = 2`. Orange nodes (9 here) are odd composites whose smallest prime factor is ≥ 3; they survive the `p = 2` pass and get crossed off by a later prime.\n\n---\n\n# Approach 1: Trial Division (Brute Force Primality Test)\n\nThe simplest way to check if a number n is prime is to test whether any integer from 2 to sqrt(n) divides it evenly.\n\n**Why sqrt(n)?** If n has a factor larger than sqrt(n), the paired factor must be smaller than sqrt(n). So we only need to check up to the square root.\n\n**Algorithm:**\n\n1. If n <= 1, return false.\n2. If n <= 3, return true.\n3. If n is divisible by 2 or 3, return false.\n4. Check all numbers of the form 6k +/- 1 up to sqrt(n). (All primes greater than 3 are of this form.)\n\nThis works perfectly for checking individual numbers, but if you need to find all primes up to n, calling this function for every number gives O(n * sqrt(n)) total time. That is where the sieve becomes essential.\n\n---\n\n# Approach 2: Sieve of Eratosthenes\n\nThe Sieve of Eratosthenes flips the problem on its head. Instead of checking each number individually, we start by assuming every number is prime, then systematically eliminate the composite ones.\n\n### Algorithm:\n\n- Create a boolean array `isPrime[0..n]`, initialized to `true`.\n- Mark `isPrime[0]` and `isPrime[1]` as `false`.\n- For each number p starting from 2:\n - If `isPrime[p]` is `true`, then p is prime.\n - Mark all multiples of p (starting from p * p) as `false`.\n- Continue until p * p > n.\n- All indices still marked `true` are prime.\n\n**Why start marking from p * p?**\n\nBecause all smaller multiples of p (like 2p, 3p, ..., (p-1) * p) have already been marked as composite by smaller primes. For example, when p = 5, we do not need to mark 10 (already handled by 2), 15 (already handled by 3), or 20 (already handled by 2). We start directly at 25.\n\n---\n\n# Approach 3: Prime Factorization Using Smallest Prime Factor (SPF) Sieve\n\nA powerful variation of the sieve precomputes the smallest prime factor for every number. Once you have this, you can factorize any number up to n in O(log n) time by repeatedly dividing by the smallest prime factor.\n\n### Algorithm:\n\n1. Create an array `spf[0..n]` where `spf[i] = i` initially (every number is its own smallest factor).\n2. Run the sieve: for each prime p, set `spf[m] = p` for all multiples m of p where `spf[m]` has not been updated yet (i.e., `spf[m] == m`).\n3. To factorize a number x: repeatedly divide x by `spf[x]` until x becomes 1.\n\nThe straightforward `factorize(x, spf)` returns a flat list of prime factors with repetitions. For example, factorizing 24 gives `[2, 2, 2, 3]`. To get the more useful `(prime, exponent)` form like `[(2, 3), (3, 1)]`, group consecutive duplicates while dividing: instead of pushing `spf[x]` every iteration, count how many times the current smallest prime divides `x` before moving on. The `Implementation` section below shows both variants.\n\nThis is especially useful when you need to factorize many numbers. Building the SPF sieve is O(n log log n), and each factorization is O(log n).\n\n---\n\n# Example Walkthrough: Sieve of Eratosthenes for n = 30\n\nLet us trace through the algorithm step by step. We start with all numbers from 2 to 30 marked as prime (T = true).\n\n\n```shell\nInitial: [2:T, 3:T, 4:T, 5:T, 6:T, 7:T, 8:T, 9:T, 10:T, 11:T, 12:T, 13:T, 14:T, 15:T,\n 16:T, 17:T, 18:T, 19:T, 20:T, 21:T, 22:T, 23:T, 24:T, 25:T, 26:T, 27:T, 28:T, 29:T, 30:T]\n```\n\n\n**Step 1: p = 2 (prime).** Mark multiples starting from 2*2 = 4: cross off 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30.\n\n\n```shell\nAfter p=2: [2:T, 3:T, 4:F, 5:T, 6:F, 7:T, 8:F, 9:T, 10:F, 11:T, 12:F, 13:T, 14:F, 15:T,\n 16:F, 17:T, 18:F, 19:T, 20:F, 21:T, 22:F, 23:T, 24:F, 25:T, 26:F, 27:T, 28:F, 29:T, 30:F]\n```\n\n\n**Step 2: p = 3 (still marked prime).** Mark multiples starting from 3*3 = 9: cross off 9, 15, 21, 27. (Note: 6, 12, 18, 24, 30 were already crossed off by 2.)\n\n\n```shell\nAfter p=3: [2:T, 3:T, 4:F, 5:T, 6:F, 7:T, 8:F, 9:F, 10:F, 11:T, 12:F, 13:T, 14:F, 15:F,\n 16:F, 17:T, 18:F, 19:T, 20:F, 21:F, 22:F, 23:T, 24:F, 25:T, 26:F, 27:F, 28:F, 29:T, 30:F]\n```\n\n\n**Step 3: p = 4 (marked false).** Skip it.\n\n**Step 4: p = 5 (still marked prime).** Mark multiples starting from 5*5 = 25: cross off 25. (30 is already crossed off.)\n\n\n```shell\nAfter p=5: [2:T, 3:T, 4:F, 5:T, 6:F, 7:T, 8:F, 9:F, 10:F, 11:T, 12:F, 13:T, 14:F, 15:F,\n 16:F, 17:T, 18:F, 19:T, 20:F, 21:F, 22:F, 23:T, 24:F, 25:F, 26:F, 27:F, 28:F, 29:T, 30:F]\n```\n\n\n**Step 5: p = 6 (stop).** Since 6*6 = 36 > 30, we are done.\n\n**Primes up to 30:** 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. That is 10 primes.\n\nNotice how few steps it took. We only needed to sieve with p = 2, 3, and 5. The sqrt(30) boundary means we stop early, and the p*p starting point means we skip redundant work.\n\n---\n\n# Implementation\n\n### Trial Division: isPrime\n\n\n```java\npublic static boolean isPrime(int n) {\n if (n <= 1) return false;\n if (n <= 3) return true;\n if (n % 2 == 0 || n % 3 == 0) return false;\n for (int i = 5; i * i <= n; i += 6) {\n if (n % i == 0 || n % (i + 2) == 0) return false;\n }\n return true;\n}\n```\n\n```python\ndef is_prime(n: int) -> bool:\n if n <= 1:\n return False\n if n <= 3:\n return True\n if n % 2 == 0 or n % 3 == 0:\n return False\n i = 5\n while i * i <= n:\n if n % i == 0 or n % (i + 2) == 0:\n return False\n i += 6\n return True\n```\n\n```cpp\nbool isPrime(int n) {\n if (n <= 1) return false;\n if (n <= 3) return true;\n if (n % 2 == 0 || n % 3 == 0) return false;\n for (int i = 5; i * i <= n; i += 6) {\n if (n % i == 0 || n % (i + 2) == 0) return false;\n }\n return true;\n}\n```\n\n```go\npackage main\n\nfunc isPrime(n int) bool {\n\tif n <= 1 {\n\t\treturn false\n\t}\n\tif n <= 3 {\n\t\treturn true\n\t}\n\tif n%2 == 0 || n%3 == 0 {\n\t\treturn false\n\t}\n\tfor i := 5; i*i <= n; i += 6 {\n\t\tif n%i == 0 || n%(i+2) == 0 {\n\t\t\treturn false\n\t\t}\n\t}\n\treturn true\n}\n```\n\n```csharp\npublic static bool IsPrime(int n) {\n if (n <= 1) return false;\n if (n <= 3) return true;\n if (n % 2 == 0 || n % 3 == 0) return false;\n for (int i = 5; i * i <= n; i += 6) {\n if (n % i == 0 || n % (i + 2) == 0) return false;\n }\n return true;\n}\n```\n\n```rust\npub struct Solution;\n\nimpl Solution {\n pub fn is_prime(n: i32) -> bool {\n if n <= 1 {\n return false;\n }\n if n <= 3 {\n return true;\n }\n if n % 2 == 0 || n % 3 == 0 {\n return false;\n }\n let mut i: i32 = 5;\n while i * i <= n {\n if n % i == 0 || n % (i + 2) == 0 {\n return false;\n }\n i += 6;\n }\n true\n }\n}\n```\n\n```javascript\nfunction isPrime(n) {\n if (n <= 1) return false;\n if (n <= 3) return true;\n if (n % 2 === 0 || n % 3 === 0) return false;\n for (let i = 5; i * i <= n; i += 6) {\n if (n % i === 0 || n % (i + 2) === 0) return false;\n }\n return true;\n}\n```\n\n```typescript\nfunction isPrime(n: number): boolean {\n if (n <= 1) return false;\n if (n <= 3) return true;\n if (n % 2 === 0 || n % 3 === 0) return false;\n for (let i = 5; i * i <= n; i += 6) {\n if (n % i === 0 || n % (i + 2) === 0) return false;\n }\n return true;\n}\n```\n\n\n---\n\n# Sieve of Eratosthenes (Count Primes, LeetCode 204)\n\nGiven an integer n, return the number of primes strictly less than n.\n\n\n```java\npublic int countPrimes(int n) {\n if (n <= 2) return 0;\n boolean[] isPrime = new boolean[n];\n Arrays.fill(isPrime, true);\n isPrime[0] = false;\n isPrime[1] = false;\n\n for (int p = 2; (long) p * p < n; p++) {\n if (isPrime[p]) {\n for (int j = p * p; j < n; j += p) {\n isPrime[j] = false;\n }\n }\n }\n\n int count = 0;\n for (boolean prime : isPrime) {\n if (prime) count++;\n }\n return count;\n}\n```\n\n```python\ndef count_primes(n: int) -> int:\n if n <= 2:\n return 0\n is_prime = [True] * n\n is_prime[0] = is_prime[1] = False\n\n p = 2\n while p * p < n:\n if is_prime[p]:\n for j in range(p * p, n, p):\n is_prime[j] = False\n p += 1\n\n return sum(is_prime)\n```\n\n```cpp\nint countPrimes(int n) {\n if (n <= 2) return 0;\n vector isPrime(n, true);\n isPrime[0] = isPrime[1] = false;\n\n for (int p = 2; (long long)p * p < n; p++) {\n if (isPrime[p]) {\n for (int j = p * p; j < n; j += p) {\n isPrime[j] = false;\n }\n }\n }\n\n return count(isPrime.begin(), isPrime.end(), true);\n}\n```\n\n```go\npackage main\n\nfunc countPrimes(n int) int {\n\tif n <= 2 {\n\t\treturn 0\n\t}\n\tisPrime := make([]bool, n)\n\tfor i := range isPrime {\n\t\tisPrime[i] = true\n\t}\n\tisPrime[0] = false\n\tisPrime[1] = false\n\n\tfor p := 2; p*p < n; p++ {\n\t\tif isPrime[p] {\n\t\t\tfor j := p * p; j < n; j += p {\n\t\t\t\tisPrime[j] = false\n\t\t\t}\n\t\t}\n\t}\n\n\tcount := 0\n\tfor _, prime := range isPrime {\n\t\tif prime {\n\t\t\tcount++\n\t\t}\n\t}\n\treturn count\n}\n```\n\n```csharp\npublic int CountPrimes(int n) {\n if (n <= 2) return 0;\n bool[] isPrime = new bool[n];\n Array.Fill(isPrime, true);\n isPrime[0] = isPrime[1] = false;\n\n for (int p = 2; (long)p * p < n; p++) {\n if (isPrime[p]) {\n for (int j = p * p; j < n; j += p) {\n isPrime[j] = false;\n }\n }\n }\n\n int count = 0;\n foreach (bool prime in isPrime) {\n if (prime) count++;\n }\n return count;\n}\n```\n\n```rust\npub struct Solution;\n\nimpl Solution {\n pub fn count_primes(n: i32) -> i32 {\n if n <= 2 {\n return 0;\n }\n let n = n as usize;\n let mut is_prime = vec![true; n];\n is_prime[0] = false;\n is_prime[1] = false;\n\n let mut p = 2usize;\n while p * p < n {\n if is_prime[p] {\n let mut j = p * p;\n while j < n {\n is_prime[j] = false;\n j += p;\n }\n }\n p += 1;\n }\n\n is_prime.into_iter().filter(|&prime| prime).count() as i32\n }\n}\n```\n\n```javascript\nfunction countPrimes(n) {\n if (n <= 2) return 0;\n const isPrime = new Array(n).fill(true);\n isPrime[0] = isPrime[1] = false;\n\n for (let p = 2; p * p < n; p++) {\n if (isPrime[p]) {\n for (let j = p * p; j < n; j += p) {\n isPrime[j] = false;\n }\n }\n }\n\n return isPrime.filter(Boolean).length;\n}\n```\n\n```typescript\nfunction countPrimes(n: number): number {\n if (n <= 2) return 0;\n const isPrime: boolean[] = new Array(n).fill(true);\n isPrime[0] = isPrime[1] = false;\n\n for (let p = 2; p * p < n; p++) {\n if (isPrime[p]) {\n for (let j = p * p; j < n; j += p) {\n isPrime[j] = false;\n }\n }\n }\n\n return isPrime.filter(Boolean).length;\n}\n```\n\n\n---\n\n# Prime Factorization Using SPF Sieve\n\n\n```java\npublic static int[] buildSPF(int n) {\n int[] spf = new int[n + 1];\n for (int i = 0; i <= n; i++) spf[i] = i;\n\n for (int p = 2; p * p <= n; p++) {\n if (spf[p] == p) { // p is prime\n for (int j = p * p; j <= n; j += p) {\n if (spf[j] == j) {\n spf[j] = p;\n }\n }\n }\n }\n return spf;\n}\n\npublic static List factorize(int x, int[] spf) {\n List factors = new ArrayList<>();\n while (x > 1) {\n factors.add(spf[x]);\n x /= spf[x];\n }\n return factors;\n}\n```\n\n```python\ndef build_spf(n: int) -> list[int]:\n spf = list(range(n + 1))\n p = 2\n while p * p <= n:\n if spf[p] == p: # p is prime\n for j in range(p * p, n + 1, p):\n if spf[j] == j:\n spf[j] = p\n p += 1\n return spf\n\ndef factorize(x: int, spf: list[int]) -> list[int]:\n factors = []\n while x > 1:\n factors.append(spf[x])\n x //= spf[x]\n return factors\n```\n\n```cpp\nvector buildSPF(int n) {\n vector spf(n + 1);\n iota(spf.begin(), spf.end(), 0); // spf[i] = i\n\n for (int p = 2; p * p <= n; p++) {\n if (spf[p] == p) {\n for (int j = p * p; j <= n; j += p) {\n if (spf[j] == j) {\n spf[j] = p;\n }\n }\n }\n }\n return spf;\n}\n\nvector factorize(int x, const vector& spf) {\n vector factors;\n while (x > 1) {\n factors.push_back(spf[x]);\n x /= spf[x];\n }\n return factors;\n}\n```\n\n```go\npackage main\n\nfunc buildSPF(n int) []int {\n\tspf := make([]int, n+1)\n\tfor i := 0; i <= n; i++ {\n\t\tspf[i] = i\n\t}\n\n\tfor p := 2; p*p <= n; p++ {\n\t\tif spf[p] == p { // p is prime\n\t\t\tfor j := p * p; j <= n; j += p {\n\t\t\t\tif spf[j] == j {\n\t\t\t\t\tspf[j] = p\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\t}\n\treturn spf\n}\n\nfunc factorize(x int, spf []int) []int {\n\tfactors := make([]int, 0)\n\tfor x > 1 {\n\t\tfactors = append(factors, spf[x])\n\t\tx /= spf[x]\n\t}\n\treturn factors\n}\n```\n\n```csharp\npublic static int[] BuildSPF(int n) {\n int[] spf = new int[n + 1];\n for (int i = 0; i <= n; i++) spf[i] = i;\n\n for (int p = 2; p * p <= n; p++) {\n if (spf[p] == p) {\n for (int j = p * p; j <= n; j += p) {\n if (spf[j] == j) {\n spf[j] = p;\n }\n }\n }\n }\n return spf;\n}\n\npublic static List Factorize(int x, int[] spf) {\n var factors = new List();\n while (x > 1) {\n factors.Add(spf[x]);\n x /= spf[x];\n }\n return factors;\n}\n```\n\n```rust\npub struct Solution;\n\nimpl Solution {\n pub fn build_spf(n: i32) -> Vec {\n let n = n as usize;\n let mut spf = vec![0_i32; n + 1];\n for i in 0..=n {\n spf[i] = i as i32;\n }\n\n let mut p = 2usize;\n while p * p <= n {\n if spf[p] == p as i32 { // p is prime\n let mut j = p * p;\n while j <= n {\n if spf[j] == j as i32 {\n spf[j] = p as i32;\n }\n j += p;\n }\n }\n p += 1;\n }\n spf\n }\n\n pub fn factorize(mut x: i32, spf: &Vec) -> Vec {\n let mut factors = Vec::new();\n while x > 1 {\n factors.push(spf[x as usize]);\n x /= spf[x as usize];\n }\n factors\n }\n}\n```\n\n```javascript\nfunction buildSPF(n) {\n const spf = Array.from({ length: n + 1 }, (_, i) => i);\n\n for (let p = 2; p * p <= n; p++) {\n if (spf[p] === p) {\n for (let j = p * p; j <= n; j += p) {\n if (spf[j] === j) {\n spf[j] = p;\n }\n }\n }\n }\n return spf;\n}\n\nfunction factorize(x, spf) {\n const factors = [];\n while (x > 1) {\n factors.push(spf[x]);\n x = Math.floor(x / spf[x]);\n }\n return factors;\n}\n```\n\n```typescript\nfunction buildSPF(n: number): number[] {\n const spf: number[] = Array.from({ length: n + 1 }, (_, i) => i);\n\n for (let p = 2; p * p <= n; p++) {\n if (spf[p] === p) {\n for (let j = p * p; j <= n; j += p) {\n if (spf[j] === j) {\n spf[j] = p;\n }\n }\n }\n }\n return spf;\n}\n\nfunction factorize(x: number, spf: number[]): number[] {\n const factors: number[] = [];\n while (x > 1) {\n factors.push(spf[x]);\n x = Math.floor(x / spf[x]);\n }\n return factors;\n}\n```\n\n\n### Grouped Variant: `(prime, exponent)` Pairs\n\nThe version above returns `[2, 2, 2, 3]` for `n = 24`. To get the canonical `[(2, 3), (3, 1)]` form, divide out the entire run of each prime before moving on:\n\n\n```java\n// Returns a list of {prime, exponent} pairs for x.\npublic static List factorizeGrouped(int x, int[] spf) {\n List result = new ArrayList<>();\n while (x > 1) {\n int p = spf[x];\n int e = 0;\n while (x % p == 0) {\n x /= p;\n e++;\n }\n result.add(new int[]{p, e});\n }\n return result;\n}\n```\n\n\nThe translation to other languages is mechanical: same outer `while x > 1`, an inner counter that increments while `spf[x]` divides `x`.\n\n---\n\n# Complexity Analysis\n\n\n| Algorithm | Time Complexity | Space Complexity | Use Case |\n|-----------|----------------|------------------|----------|\n| Trial Division | O(sqrt(n)) per query | O(1) | Checking a single number |\n| Sieve of Eratosthenes | O(n log log n) | O(n) | Finding all primes up to n |\n| SPF Sieve (build) | O(n log log n) | O(n) | Precomputing smallest prime factors |\n| SPF Factorization | O(log n) per query | O(log n) | Factorizing after sieve is built |\n\n\n**Why O(n log log n) for the sieve?** The total number of composite markings is:\n\nn/2 + n/3 + n/5 + n/7 + ... (sum over all primes p <= n)\n\nBy Mertens' theorem, the sum of reciprocals of primes up to n is approximately log(log(n)). Multiplying by n gives O(n log log n). In practice, this is nearly linear. For n = 10 million, log(log(n)) is about 3.\n\n---\n\n# Choosing Between the Three\n\nThe three algorithms have overlapping use cases but very different cost profiles:\n\n- **Trial division** is for one-off primality checks on values that may be larger than what you can sieve. Use it when you have a single number up to roughly 10^12 (the inner loop runs up to sqrt(n) ≈ 10^6, which finishes in milliseconds).\n- **Sieve of Eratosthenes** is for \"tell me all primes up to N\" or any problem that does many primality lookups on values in a fixed range. The boolean array fits comfortably in memory up to N ≈ 10^8; beyond that, switch to a bitset or segmented sieve.\n- **SPF sieve** is for repeated *factorization* queries on values up to N. The build cost is the same as the regular sieve, but each factorization is O(log n) instead of O(sqrt(n)). Use it when the same number range is factorized many times (divisor counts, multiplicative-function sums, factor-of-each-element problems).\n\nA useful rule of thumb: if the problem range fits in a sieve and you need primality or factorization for many values in that range, precompute once. If you have a single huge number outside any reasonable sieve range, fall back to trial division (and consider Pollard's rho if `n > 10^14`, which is beyond this chapter).","pageType":"dsa"}

Prime Sieve

Get Premium