What is the pricing and subscription model for Hi👋SpeedAlgo?

The entire core curriculum of 13 patterns and 225 practice problems is 100% free to access with no credit card required. New accounts get 40 free coins once, the daily claim adds +20 coins once a day, and inviting a friend earns you +25 coins when they complete their first practice step. These are the only ways to earn coins. Each AI coach question costs 1-5 coins, priced by the server according to its size. AI coaching is free with your own Google Gemini, OpenAI or OpenRouter API key (BYOK). Coins also unlock extras for 24 hours: a Recall hint level (1 coin), a Solve solution reveal (2), a LeetCode problem card's solutions (1) and a pattern's extra canonical problems (1). Nothing on the site is sold for money: coins can only be earned, never bought.

What is the refund and cancellation policy?

Hi👋SpeedAlgo sells nothing for money: there are no subscriptions, renewals or charges, so there is nothing to cancel or refund. Nothing on the site is sold for money: coins can only be earned, never bought.

Who creates and maintains the curriculum?

Hi👋SpeedAlgo is developed and maintained by Hi👋WebEnterprise (https://hiwebenterprise.com), an engineering organization focused on developer education, deliberate practice methodologies, and cognitive ergonomics for technical interviews.

How does Hi👋SpeedAlgo prepare candidates for senior and staff SWE interviews?

Rather than rote LeetCode grinding, Hi👋SpeedAlgo uses deliberate practice for each pattern: learn the loop invariant, Big-O proof and edge cases from a side-by-side template and a step-by-step debugger, rebuild the template from memory, then solve a new problem on your own against a graded test suite.

Theory Context•Math & Geometry

P3MediumMental model~3 min speedrun

Count Primes (LC 204)(opens leetcode.com)

You receive one integer n. Count how many prime numbers sit below n, and hand that count back.

Recall that a prime is any whole number bigger than 1 whose only positive divisors are 1 and the number itself.

Example 1

Input:n = 10

Output:4

There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

Sieve of Eratosthenes

upper bound n ➔ boolean sieve array ➔ prime count

Spot it when: You need to know which of many numbers up to a known limit are prime (counting primes, pairing primes, checking many values), not just one number.

Python

1	def count_primes(n: int) -> int:
2	"""Sieve of Eratosthenes: counts primes strictly below n.
3	Time: O(N log log N) \| Space: O(N)
4	"""
5	if n <= 2:
6	return 0 # No primes below 2
7
8	is_prime = [True] * n
9	is_prime[0] = is_prime[1] = False # 0 and 1 are not prime
10
11	for p in range(2, int(n ** 0.5) + 1): # Factors above sqrt(n) were already crossed out
12	if is_prime[p]:
13	for multiple in range(p * p, n, p): # Start at p*p: smaller multiples have a smaller factor
14	is_prime[multiple] = False
15
16	return sum(is_prime)

Invariant: When the loop reaches p, is_prime[q] is already correct for every q < p * p, so is_prime[p] is True exactly when p is prime.

A number is composite exactly when it has a prime factor no larger than its square root, so cross off multiples only for primes p up to sqrt(n). Start each crossing at p * p: every smaller multiple p * k with k < p was already crossed off by a smaller prime factor of k. Whatever is still True in is_prime is prime. The trap is 0 and 1: they start True like every slot, but no crossing ever reaches them, so set both to False first or the count comes out 2 too high.

See it run

Sieve of Eratosthenes, step by step

p -primes left 30

Each cell is one slot of is_prime, read left to right in rows of 6. The number is the row label plus the column offset. An x means the slot is False.

p the prime whose multiples are crossed now
crossed a number marked False in this step
skip a value of p that is already crossed, so its loop is skipped
prime a number still True at the end

is_prime = [True] * 30. Every slot from 0 to 29 starts as True, so every number is still a candidate.

1 / 10

Gotchas1 of 5

The trap
Gotcha 1: Leaving is_prime[0] and is_prime[1] as True
Mistake
```
is_prime = [True] * n
```
Fix
```
is_prime = [True] * n
is_prime[0] = is_prime[1] = False
```
What happens: Every slot starts True. Crossing out starts at p * p, which is at least 4. So no step ever reaches 0 or 1. Without the line, sum(is_prime) counts 0 and 1 as primes, and the count is 2 too high.
Example: n = 10
Mistake: returns 6Fix: returns 4
Gotcha 2: Making the table [True] * (n + 1)
Mistake
```
is_prime = [True] * (n + 1)
```
Fix
```
is_prime = [True] * n
```
What happens: Count Primes (LC 204) counts the primes strictly less than n. With n + 1 slots, the table also has a slot for n itself. The loop range(p * p, n, p) stops before n, so that slot is never crossed out. sum(is_prime) then counts n as a prime, even when it is not. The same definition explains if n <= 2: return 0, because no prime is less than 2.
Example: n = 10
Mistake: returns 5Fix: returns 4
Gotcha 3: Stopping p at int(n ** 0.5) without the + 1
Mistake
```
for p in range(2, int(n ** 0.5)):
```
Fix
```
for p in range(2, int(n ** 0.5) + 1):
```
What happens: range stops before its end value. Without + 1, p never takes the value int(n ** 0.5) itself. For n = 10, that value is 3, so 9 is never crossed out. Any end above the square root is correct. Looping p up to n also works, but it is slower.
Example: n = 10
Mistake: returns 5Fix: returns 4
Gotcha 4: Starting the crossing at 2 * p instead of p * p
Mistake
```
for multiple in range(2 * p, n, p):
```
Fix
```
for multiple in range(p * p, n, p):
```
What happens: Every multiple p * k with k < p has a prime factor smaller than p. That smaller prime already crossed it out. Starting at 2 * p crosses those numbers out again. The count is the same, and only the time grows.
Gotcha 5: Building a sieve to test only one or two numbers
What happens: The sieve fills a table of n slots, so it costs O(n log log n) time and O(n) space. To test one number x, trial division by every value up to the square root of x is simpler. The sieve pays off when you test many numbers below n.

Not this one if…

Only a few fixed primes appear and the length can reach 10^15, as in Count Good Numbers (LC 1922): the hard part is one huge power, not finding primes. See Fast Power

Deep Dive

Why crossing out multiples finds every prime

A prime is a number above 1 that has no divisor except 1 and itself. A composite number is a number above 1 that is not prime. Every composite number has a prime factor. So if you cross out all multiples of every prime, only primes remain.

is_prime[q] means "no smaller prime has divided q so far". When the loop reaches p and is_prime[p] is still True, no prime below p divides p. So p is prime. This is the invariant: is_prime[q] is already correct for every q < p * p.

Why q < p * p? A composite q has a prime factor of at most sqrt(q). If q < p * p, that factor is smaller than p. The loop already crossed q out when it handled that factor.

Why the crossing starts at p * p and p stops at the square root

A multiple p * k with k < p has the factor k. The smallest prime factor of k is smaller than p, so a smaller prime already crossed p * k out. The first multiple of p that nothing smaller has touched is p * p.

The same fact ends the outer loop. A composite number below n has a prime factor of at most sqrt(n). The outer loop range(2, int(n ** 0.5) + 1) visits all of those primes. A prime p above sqrt(n) has p * p >= n, so its inner loop would be empty.

The + 1 is needed because range stops before its end value. For n = 10, int(10 ** 0.5) is 3. Without + 1, p = 3 never runs, and 9 stays in the table as a prime. The answer is 5 instead of 4.

Trace for n = 30: 10 primes below 30

The table has slots 0 to 29. First is_prime[0] = is_prime[1] = False. The loop p runs from 2 to int(30 ** 0.5), which is 5.

p = 2 is prime. It crosses 4, 6, 8, ... 28, which is 13 numbers. p = 3 is prime. It starts at 9 and crosses 9, 15, 21 and 27. The numbers 12, 18 and 24 were already crossed by 2. p = 4 is crossed out, so its loop is skipped. p = 5 is prime and crosses only 25, because 30 is outside the table.

The numbers still True are 2, 3, 5, 7, 11, 13, 17, 19, 23 and 29. That is 10 primes, and sum(is_prime) returns 10. For the Count Primes (LC 204) example n = 10, the same steps leave 2, 3, 5 and 7, so the answer is 4.

Without the line for 0 and 1, the sum would count them too and return 12 for n = 30, or 6 for n = 10.

Cost: O(n log log n) time and `O(n)` space

The space is the table: n booleans. The time is the number of crossings plus the final sum.

Prime p crosses about n / p numbers. The total over all primes up to n is n times the sum of 1 / p, and that sum grows like log log n. This is why the cost is O(n log log n), only a little more than O(n).

Measured with the card's own loop: for n = 100, the crossings start at p * p and make 102 writes. Starting at 2 * p would make 111 writes for the same answer. For n = 10**6, the sieve makes about 2.1 million writes for a table of one million slots.

The table itself limits the sieve. It needs n slots, so it suits limits up to roughly tens of millions. For one number x, trial division up to sqrt(x) is simpler and uses no table.

60-Second Pitch

"I need the primes below n, so I build a boolean table is_prime of n slots and set slots 0 and 1 to False. For each p from 2 to the integer square root of n, if is_prime[p] is still True, I cross out its multiples starting at p * p. A smaller multiple has a smaller prime factor, so it was already crossed. The outer loop stops at the square root because every composite number below n has a prime factor of at most that size. The answer is sum(is_prime). The time is O(n log log n) and the space is O(n). I check three things: slots 0 and 1, the table size n and not n + 1, and the + 1 in the range. For n = 10, the answer is 4."

Common Questions

Why does the inner loop start at p * p and not at 2 * p?: A multiple p * k with k < p has a prime factor smaller than p, and that smaller prime already crossed it out. Starting at p * p skips those repeated writes. For n = 100 it saves 9 writes. The answer is the same either way.
Why can the outer loop stop at the square root of n?: A composite number below n has a prime factor of at most sqrt(n). So crossing out the multiples of primes up to sqrt(n) removes every composite number. A larger p has p * p >= n, so its inner loop does nothing.
What is the time and space complexity, and why is the time not O(n^2)?: Time is O(n log log n) and space is O(n). Prime p writes about n / p slots, and the sum of n / p over primes up to n is about n log log n. Only primes cross out multiples, so composite values of p add no work.
When would you not use a sieve?: Use trial division when you test one or two numbers, because the sieve builds a table of n slots first. Also avoid it when the limit is too large for memory. The sieve pays off when many values below one limit need a prime test.
Why does Count Primes (LC 204) use [True] * n and not n + 1?: The problem counts primes strictly less than n, so the table needs slots 0 to n - 1. With n + 1 slots, slot n is never crossed out, because the inner loop stops before n. A non-prime n is then counted as a prime.

SWE Reasoning

Spot it

The problem asks how many numbers below a known limit are prime (Count Primes (LC 204)).
The problem needs a prime test for many values below one limit, so one table can answer all of them (Prime Arrangements (LC 1175), Prime Subtraction Operation (LC 2601), Prime Pairs With Target Sum (LC 2761)).
The limit n is small enough to hold a boolean table in memory.
The test is a property of each number (prime or not), not the value of one huge power. For a huge power, use Fast Power.

The invariant, step by step

is_prime has n slots, all True. Slots 0 and 1 are set to False at once.
The loop takes p from 2 upward. When it reaches p, every slot q < p * p is correct.
If is_prime[p] is True, no smaller prime divides p, so p is prime.
The inner loop sets is_prime[multiple] to False for p * p, p * p + p, and so on below n.
After that, every slot q < (p + 1) * (p + 1) is correct, because a composite q in that range has a prime factor of at most p.
When p passes int(n ** 0.5), every slot below n is correct, and sum(is_prime) counts the primes.

Traps

Slots 0 and 1 left as True. No crossing starts below 4. sum(is_prime) counts both and is 2 too high. count_primes(10) returns 6 instead of 4.
Table of n + 1 slots. Count Primes (LC 204) counts primes strictly below n. The extra slot for n is never crossed, so a non-prime n is counted. count_primes(10) returns 5.
range(2, int(n ** 0.5)) without + 1. p never reaches the integer square root. For n = 10, 9 is not crossed and the answer is 5.
Crossing from 2 * p. The answer is correct, but the code writes to the same slots again. For n = 100, it makes 111 writes instead of 102.
A sieve for one number. Building a table of n slots to test one x costs more than trial division up to sqrt(x).

Practice

Canonical LeetCode:Count Primes (LC 204)Prime Arrangements (LC 1175)Prime Subtraction Operation (LC 2601)Prime Pairs With Target Sum (LC 2761)

Theory Context•Math & Geometry

P3MediumMental model~3 min speedrun

Count Primes (LC 204)(opens leetcode.com)

You receive one integer n. Count how many prime numbers sit below n, and hand that count back.

Recall that a prime is any whole number bigger than 1 whose only positive divisors are 1 and the number itself.

Example 1

Input:n = 10

Output:4

There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

Sieve of Eratosthenes

upper bound n ➔ boolean sieve array ➔ prime count

Spot it when: You need to know which of many numbers up to a known limit are prime (counting primes, pairing primes, checking many values), not just one number.

Sieve of Eratosthenes

Python

1	def count_primes(n: int) -> int:
2	"""Sieve of Eratosthenes: counts primes strictly below n.
3	Time: O(N log log N) \| Space: O(N)
4	"""
5	if n <= 2:
6	return 0 # No primes below 2
7
8	is_prime = [True] * n
9	is_prime[0] = is_prime[1] = False # 0 and 1 are not prime
10
11	for p in range(2, int(n ** 0.5) + 1): # Factors above sqrt(n) were already crossed out
12	if is_prime[p]:
13	for multiple in range(p * p, n, p): # Start at p*p: smaller multiples have a smaller factor
14	is_prime[multiple] = False
15
16	return sum(is_prime)

Invariant: When the loop reaches p, is_prime[q] is already correct for every q < p * p, so is_prime[p] is True exactly when p is prime.

See it run

Sieve of Eratosthenes, step by step

p -primes left 30

Each cell is one slot of is_prime, read left to right in rows of 6. The number is the row label plus the column offset. An x means the slot is False.

p the prime whose multiples are crossed now
crossed a number marked False in this step
skip a value of p that is already crossed, so its loop is skipped
prime a number still True at the end

is_prime = [True] * 30. Every slot from 0 to 29 starts as True, so every number is still a candidate.

1 / 10

Gotchas1 of 5

The trap
Gotcha 1: Leaving is_prime[0] and is_prime[1] as True
Mistake
```
is_prime = [True] * n
```
Fix
```
is_prime = [True] * n
is_prime[0] = is_prime[1] = False
```
What happens: Every slot starts True. Crossing out starts at p * p, which is at least 4. So no step ever reaches 0 or 1. Without the line, sum(is_prime) counts 0 and 1 as primes, and the count is 2 too high.
Example: n = 10
Mistake: returns 6Fix: returns 4
Gotcha 2: Making the table [True] * (n + 1)
Mistake
```
is_prime = [True] * (n + 1)
```
Fix
```
is_prime = [True] * n
```
What happens: Count Primes (LC 204) counts the primes strictly less than n. With n + 1 slots, the table also has a slot for n itself. The loop range(p * p, n, p) stops before n, so that slot is never crossed out. sum(is_prime) then counts n as a prime, even when it is not. The same definition explains if n <= 2: return 0, because no prime is less than 2.
Example: n = 10
Mistake: returns 5Fix: returns 4
Gotcha 3: Stopping p at int(n ** 0.5) without the + 1
Mistake
```
for p in range(2, int(n ** 0.5)):
```
Fix
```
for p in range(2, int(n ** 0.5) + 1):
```
What happens: range stops before its end value. Without + 1, p never takes the value int(n ** 0.5) itself. For n = 10, that value is 3, so 9 is never crossed out. Any end above the square root is correct. Looping p up to n also works, but it is slower.
Example: n = 10
Mistake: returns 5Fix: returns 4
Gotcha 4: Starting the crossing at 2 * p instead of p * p
Mistake
```
for multiple in range(2 * p, n, p):
```
Fix
```
for multiple in range(p * p, n, p):
```
What happens: Every multiple p * k with k < p has a prime factor smaller than p. That smaller prime already crossed it out. Starting at 2 * p crosses those numbers out again. The count is the same, and only the time grows.
Gotcha 5: Building a sieve to test only one or two numbers
What happens: The sieve fills a table of n slots, so it costs O(n log log n) time and O(n) space. To test one number x, trial division by every value up to the square root of x is simpler. The sieve pays off when you test many numbers below n.

Not this one if…

Only a few fixed primes appear and the length can reach 10^15, as in Count Good Numbers (LC 1922): the hard part is one huge power, not finding primes. See Fast Power

Deep Dive

Why crossing out multiples finds every prime

Why q < p * p? A composite q has a prime factor of at most sqrt(q). If q < p * p, that factor is smaller than p. The loop already crossed q out when it handled that factor.

Why the crossing starts at p * p and p stops at the square root

Trace for n = 30: 10 primes below 30

The table has slots 0 to 29. First is_prime[0] = is_prime[1] = False. The loop p runs from 2 to int(30 ** 0.5), which is 5.

Without the line for 0 and 1, the sum would count them too and return 12 for n = 30, or 6 for n = 10.

Cost: O(n log log n) time and `O(n)` space

The space is the table: n booleans. The time is the number of crossings plus the final sum.

The table itself limits the sieve. It needs n slots, so it suits limits up to roughly tens of millions. For one number x, trial division up to sqrt(x) is simpler and uses no table.

60-Second Pitch

Common Questions

Why does the inner loop start at p * p and not at 2 * p?: A multiple p * k with k < p has a prime factor smaller than p, and that smaller prime already crossed it out. Starting at p * p skips those repeated writes. For n = 100 it saves 9 writes. The answer is the same either way.
Why can the outer loop stop at the square root of n?: A composite number below n has a prime factor of at most sqrt(n). So crossing out the multiples of primes up to sqrt(n) removes every composite number. A larger p has p * p >= n, so its inner loop does nothing.
What is the time and space complexity, and why is the time not O(n^2)?: Time is O(n log log n) and space is O(n). Prime p writes about n / p slots, and the sum of n / p over primes up to n is about n log log n. Only primes cross out multiples, so composite values of p add no work.
When would you not use a sieve?: Use trial division when you test one or two numbers, because the sieve builds a table of n slots first. Also avoid it when the limit is too large for memory. The sieve pays off when many values below one limit need a prime test.
Why does Count Primes (LC 204) use [True] * n and not n + 1?: The problem counts primes strictly less than n, so the table needs slots 0 to n - 1. With n + 1 slots, slot n is never crossed out, because the inner loop stops before n. A non-prime n is then counted as a prime.

SWE Reasoning

Spot it

The problem asks how many numbers below a known limit are prime (Count Primes (LC 204)).
The problem needs a prime test for many values below one limit, so one table can answer all of them (Prime Arrangements (LC 1175), Prime Subtraction Operation (LC 2601), Prime Pairs With Target Sum (LC 2761)).
The limit n is small enough to hold a boolean table in memory.
The test is a property of each number (prime or not), not the value of one huge power. For a huge power, use Fast Power.

The invariant, step by step

is_prime has n slots, all True. Slots 0 and 1 are set to False at once.
The loop takes p from 2 upward. When it reaches p, every slot q < p * p is correct.
If is_prime[p] is True, no smaller prime divides p, so p is prime.
The inner loop sets is_prime[multiple] to False for p * p, p * p + p, and so on below n.
After that, every slot q < (p + 1) * (p + 1) is correct, because a composite q in that range has a prime factor of at most p.
When p passes int(n ** 0.5), every slot below n is correct, and sum(is_prime) counts the primes.

Traps

Slots 0 and 1 left as True. No crossing starts below 4. sum(is_prime) counts both and is 2 too high. count_primes(10) returns 6 instead of 4.
Table of n + 1 slots. Count Primes (LC 204) counts primes strictly below n. The extra slot for n is never crossed, so a non-prime n is counted. count_primes(10) returns 5.
range(2, int(n ** 0.5)) without + 1. p never reaches the integer square root. For n = 10, 9 is not crossed and the answer is 5.
Crossing from 2 * p. The answer is correct, but the code writes to the same slots again. For n = 100, it makes 111 writes instead of 102.
A sieve for one number. Building a table of n slots to test one x costs more than trial division up to sqrt(x).

Practice

Canonical LeetCode:Count Primes (LC 204)Prime Arrangements (LC 1175)Prime Subtraction Operation (LC 2601)Prime Pairs With Target Sum (LC 2761)

Theory Context•Math & Geometry

P3MediumMental model~3 min speedrun

Count Primes (LC 204)(opens leetcode.com)

You receive one integer n. Count how many prime numbers sit below n, and hand that count back.

Recall that a prime is any whole number bigger than 1 whose only positive divisors are 1 and the number itself.

Example 1

Input:n = 10

Output:4

There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

Sieve of Eratosthenes

upper bound n ➔ boolean sieve array ➔ prime count

Spot it when: You need to know which of many numbers up to a known limit are prime (counting primes, pairing primes, checking many values), not just one number.

Sieve of Eratosthenes

Python

1	def count_primes(n: int) -> int:
2	"""Sieve of Eratosthenes: counts primes strictly below n.
3	Time: O(N log log N) \| Space: O(N)
4	"""
5	if n <= 2:
6	return 0 # No primes below 2
7
8	is_prime = [True] * n
9	is_prime[0] = is_prime[1] = False # 0 and 1 are not prime
10
11	for p in range(2, int(n ** 0.5) + 1): # Factors above sqrt(n) were already crossed out
12	if is_prime[p]:
13	for multiple in range(p * p, n, p): # Start at p*p: smaller multiples have a smaller factor
14	is_prime[multiple] = False
15
16	return sum(is_prime)

Invariant: When the loop reaches p, is_prime[q] is already correct for every q < p * p, so is_prime[p] is True exactly when p is prime.

See it run

Sieve of Eratosthenes, step by step

p -primes left 30

Each cell is one slot of is_prime, read left to right in rows of 6. The number is the row label plus the column offset. An x means the slot is False.

p the prime whose multiples are crossed now
crossed a number marked False in this step
skip a value of p that is already crossed, so its loop is skipped
prime a number still True at the end

is_prime = [True] * 30. Every slot from 0 to 29 starts as True, so every number is still a candidate.

1 / 10

Gotchas1 of 5

The trap
Gotcha 1: Leaving is_prime[0] and is_prime[1] as True
Mistake
```
is_prime = [True] * n
```
Fix
```
is_prime = [True] * n
is_prime[0] = is_prime[1] = False
```
What happens: Every slot starts True. Crossing out starts at p * p, which is at least 4. So no step ever reaches 0 or 1. Without the line, sum(is_prime) counts 0 and 1 as primes, and the count is 2 too high.
Example: n = 10
Mistake: returns 6Fix: returns 4
Gotcha 2: Making the table [True] * (n + 1)
Mistake
```
is_prime = [True] * (n + 1)
```
Fix
```
is_prime = [True] * n
```
What happens: Count Primes (LC 204) counts the primes strictly less than n. With n + 1 slots, the table also has a slot for n itself. The loop range(p * p, n, p) stops before n, so that slot is never crossed out. sum(is_prime) then counts n as a prime, even when it is not. The same definition explains if n <= 2: return 0, because no prime is less than 2.
Example: n = 10
Mistake: returns 5Fix: returns 4
Gotcha 3: Stopping p at int(n ** 0.5) without the + 1
Mistake
```
for p in range(2, int(n ** 0.5)):
```
Fix
```
for p in range(2, int(n ** 0.5) + 1):
```
What happens: range stops before its end value. Without + 1, p never takes the value int(n ** 0.5) itself. For n = 10, that value is 3, so 9 is never crossed out. Any end above the square root is correct. Looping p up to n also works, but it is slower.
Example: n = 10
Mistake: returns 5Fix: returns 4
Gotcha 4: Starting the crossing at 2 * p instead of p * p
Mistake
```
for multiple in range(2 * p, n, p):
```
Fix
```
for multiple in range(p * p, n, p):
```
What happens: Every multiple p * k with k < p has a prime factor smaller than p. That smaller prime already crossed it out. Starting at 2 * p crosses those numbers out again. The count is the same, and only the time grows.
Gotcha 5: Building a sieve to test only one or two numbers
What happens: The sieve fills a table of n slots, so it costs O(n log log n) time and O(n) space. To test one number x, trial division by every value up to the square root of x is simpler. The sieve pays off when you test many numbers below n.

Not this one if…

Only a few fixed primes appear and the length can reach 10^15, as in Count Good Numbers (LC 1922): the hard part is one huge power, not finding primes. See Fast Power

Deep Dive

Why crossing out multiples finds every prime

Why q < p * p? A composite q has a prime factor of at most sqrt(q). If q < p * p, that factor is smaller than p. The loop already crossed q out when it handled that factor.

Why the crossing starts at p * p and p stops at the square root

Trace for n = 30: 10 primes below 30

The table has slots 0 to 29. First is_prime[0] = is_prime[1] = False. The loop p runs from 2 to int(30 ** 0.5), which is 5.

Without the line for 0 and 1, the sum would count them too and return 12 for n = 30, or 6 for n = 10.

Cost: O(n log log n) time and `O(n)` space

The space is the table: n booleans. The time is the number of crossings plus the final sum.

The table itself limits the sieve. It needs n slots, so it suits limits up to roughly tens of millions. For one number x, trial division up to sqrt(x) is simpler and uses no table.

60-Second Pitch

Common Questions

Why does the inner loop start at p * p and not at 2 * p?: A multiple p * k with k < p has a prime factor smaller than p, and that smaller prime already crossed it out. Starting at p * p skips those repeated writes. For n = 100 it saves 9 writes. The answer is the same either way.
Why can the outer loop stop at the square root of n?: A composite number below n has a prime factor of at most sqrt(n). So crossing out the multiples of primes up to sqrt(n) removes every composite number. A larger p has p * p >= n, so its inner loop does nothing.
What is the time and space complexity, and why is the time not O(n^2)?: Time is O(n log log n) and space is O(n). Prime p writes about n / p slots, and the sum of n / p over primes up to n is about n log log n. Only primes cross out multiples, so composite values of p add no work.
When would you not use a sieve?: Use trial division when you test one or two numbers, because the sieve builds a table of n slots first. Also avoid it when the limit is too large for memory. The sieve pays off when many values below one limit need a prime test.
Why does Count Primes (LC 204) use [True] * n and not n + 1?: The problem counts primes strictly less than n, so the table needs slots 0 to n - 1. With n + 1 slots, slot n is never crossed out, because the inner loop stops before n. A non-prime n is then counted as a prime.

SWE Reasoning

Spot it

The problem asks how many numbers below a known limit are prime (Count Primes (LC 204)).
The problem needs a prime test for many values below one limit, so one table can answer all of them (Prime Arrangements (LC 1175), Prime Subtraction Operation (LC 2601), Prime Pairs With Target Sum (LC 2761)).
The limit n is small enough to hold a boolean table in memory.
The test is a property of each number (prime or not), not the value of one huge power. For a huge power, use Fast Power.

The invariant, step by step

is_prime has n slots, all True. Slots 0 and 1 are set to False at once.
The loop takes p from 2 upward. When it reaches p, every slot q < p * p is correct.
If is_prime[p] is True, no smaller prime divides p, so p is prime.
The inner loop sets is_prime[multiple] to False for p * p, p * p + p, and so on below n.
After that, every slot q < (p + 1) * (p + 1) is correct, because a composite q in that range has a prime factor of at most p.
When p passes int(n ** 0.5), every slot below n is correct, and sum(is_prime) counts the primes.

Traps

Slots 0 and 1 left as True. No crossing starts below 4. sum(is_prime) counts both and is 2 too high. count_primes(10) returns 6 instead of 4.
Table of n + 1 slots. Count Primes (LC 204) counts primes strictly below n. The extra slot for n is never crossed, so a non-prime n is counted. count_primes(10) returns 5.
range(2, int(n ** 0.5)) without + 1. p never reaches the integer square root. For n = 10, 9 is not crossed and the answer is 5.
Crossing from 2 * p. The answer is correct, but the code writes to the same slots again. For n = 100, it makes 111 writes instead of 102.
A sieve for one number. Building a table of n slots to test one x costs more than trial division up to sqrt(x).

Practice

Canonical LeetCode:Count Primes (LC 204)Prime Arrangements (LC 1175)Prime Subtraction Operation (LC 2601)Prime Pairs With Target Sum (LC 2761)

Theory Context•Math & Geometry

P3MediumMental model~3 min speedrun

Count Primes (LC 204)(opens leetcode.com)

You receive one integer n. Count how many prime numbers sit below n, and hand that count back.

Recall that a prime is any whole number bigger than 1 whose only positive divisors are 1 and the number itself.

Example 1

Input:n = 10

Output:4

There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

Sieve of Eratosthenes

upper bound n ➔ boolean sieve array ➔ prime count

Spot it when: You need to know which of many numbers up to a known limit are prime (counting primes, pairing primes, checking many values), not just one number.

Sieve of Eratosthenes

Python

1	def count_primes(n: int) -> int:
2	"""Sieve of Eratosthenes: counts primes strictly below n.
3	Time: O(N log log N) \| Space: O(N)
4	"""
5	if n <= 2:
6	return 0 # No primes below 2
7
8	is_prime = [True] * n
9	is_prime[0] = is_prime[1] = False # 0 and 1 are not prime
10
11	for p in range(2, int(n ** 0.5) + 1): # Factors above sqrt(n) were already crossed out
12	if is_prime[p]:
13	for multiple in range(p * p, n, p): # Start at p*p: smaller multiples have a smaller factor
14	is_prime[multiple] = False
15
16	return sum(is_prime)

Invariant: When the loop reaches p, is_prime[q] is already correct for every q < p * p, so is_prime[p] is True exactly when p is prime.

See it run

Sieve of Eratosthenes, step by step

p -primes left 30

Each cell is one slot of is_prime, read left to right in rows of 6. The number is the row label plus the column offset. An x means the slot is False.

p the prime whose multiples are crossed now
crossed a number marked False in this step
skip a value of p that is already crossed, so its loop is skipped
prime a number still True at the end

is_prime = [True] * 30. Every slot from 0 to 29 starts as True, so every number is still a candidate.

1 / 10

Gotchas1 of 5

The trap
Gotcha 1: Leaving is_prime[0] and is_prime[1] as True
Mistake
```
is_prime = [True] * n
```
Fix
```
is_prime = [True] * n
is_prime[0] = is_prime[1] = False
```
What happens: Every slot starts True. Crossing out starts at p * p, which is at least 4. So no step ever reaches 0 or 1. Without the line, sum(is_prime) counts 0 and 1 as primes, and the count is 2 too high.
Example: n = 10
Mistake: returns 6Fix: returns 4
Gotcha 2: Making the table [True] * (n + 1)
Mistake
```
is_prime = [True] * (n + 1)
```
Fix
```
is_prime = [True] * n
```
What happens: Count Primes (LC 204) counts the primes strictly less than n. With n + 1 slots, the table also has a slot for n itself. The loop range(p * p, n, p) stops before n, so that slot is never crossed out. sum(is_prime) then counts n as a prime, even when it is not. The same definition explains if n <= 2: return 0, because no prime is less than 2.
Example: n = 10
Mistake: returns 5Fix: returns 4
Gotcha 3: Stopping p at int(n ** 0.5) without the + 1
Mistake
```
for p in range(2, int(n ** 0.5)):
```
Fix
```
for p in range(2, int(n ** 0.5) + 1):
```
What happens: range stops before its end value. Without + 1, p never takes the value int(n ** 0.5) itself. For n = 10, that value is 3, so 9 is never crossed out. Any end above the square root is correct. Looping p up to n also works, but it is slower.
Example: n = 10
Mistake: returns 5Fix: returns 4
Gotcha 4: Starting the crossing at 2 * p instead of p * p
Mistake
```
for multiple in range(2 * p, n, p):
```
Fix
```
for multiple in range(p * p, n, p):
```
What happens: Every multiple p * k with k < p has a prime factor smaller than p. That smaller prime already crossed it out. Starting at 2 * p crosses those numbers out again. The count is the same, and only the time grows.
Gotcha 5: Building a sieve to test only one or two numbers
What happens: The sieve fills a table of n slots, so it costs O(n log log n) time and O(n) space. To test one number x, trial division by every value up to the square root of x is simpler. The sieve pays off when you test many numbers below n.

Not this one if…

Only a few fixed primes appear and the length can reach 10^15, as in Count Good Numbers (LC 1922): the hard part is one huge power, not finding primes. See Fast Power

Deep Dive

Why crossing out multiples finds every prime

Why q < p * p? A composite q has a prime factor of at most sqrt(q). If q < p * p, that factor is smaller than p. The loop already crossed q out when it handled that factor.

Why the crossing starts at p * p and p stops at the square root

Trace for n = 30: 10 primes below 30

The table has slots 0 to 29. First is_prime[0] = is_prime[1] = False. The loop p runs from 2 to int(30 ** 0.5), which is 5.

Without the line for 0 and 1, the sum would count them too and return 12 for n = 30, or 6 for n = 10.

Cost: O(n log log n) time and `O(n)` space

The space is the table: n booleans. The time is the number of crossings plus the final sum.

The table itself limits the sieve. It needs n slots, so it suits limits up to roughly tens of millions. For one number x, trial division up to sqrt(x) is simpler and uses no table.

60-Second Pitch

Common Questions

Why does the inner loop start at p * p and not at 2 * p?: A multiple p * k with k < p has a prime factor smaller than p, and that smaller prime already crossed it out. Starting at p * p skips those repeated writes. For n = 100 it saves 9 writes. The answer is the same either way.
Why can the outer loop stop at the square root of n?: A composite number below n has a prime factor of at most sqrt(n). So crossing out the multiples of primes up to sqrt(n) removes every composite number. A larger p has p * p >= n, so its inner loop does nothing.
What is the time and space complexity, and why is the time not O(n^2)?: Time is O(n log log n) and space is O(n). Prime p writes about n / p slots, and the sum of n / p over primes up to n is about n log log n. Only primes cross out multiples, so composite values of p add no work.
When would you not use a sieve?: Use trial division when you test one or two numbers, because the sieve builds a table of n slots first. Also avoid it when the limit is too large for memory. The sieve pays off when many values below one limit need a prime test.
Why does Count Primes (LC 204) use [True] * n and not n + 1?: The problem counts primes strictly less than n, so the table needs slots 0 to n - 1. With n + 1 slots, slot n is never crossed out, because the inner loop stops before n. A non-prime n is then counted as a prime.

SWE Reasoning

Spot it

The problem asks how many numbers below a known limit are prime (Count Primes (LC 204)).
The problem needs a prime test for many values below one limit, so one table can answer all of them (Prime Arrangements (LC 1175), Prime Subtraction Operation (LC 2601), Prime Pairs With Target Sum (LC 2761)).
The limit n is small enough to hold a boolean table in memory.
The test is a property of each number (prime or not), not the value of one huge power. For a huge power, use Fast Power.

The invariant, step by step

is_prime has n slots, all True. Slots 0 and 1 are set to False at once.
The loop takes p from 2 upward. When it reaches p, every slot q < p * p is correct.
If is_prime[p] is True, no smaller prime divides p, so p is prime.
The inner loop sets is_prime[multiple] to False for p * p, p * p + p, and so on below n.
After that, every slot q < (p + 1) * (p + 1) is correct, because a composite q in that range has a prime factor of at most p.
When p passes int(n ** 0.5), every slot below n is correct, and sum(is_prime) counts the primes.

Traps

Slots 0 and 1 left as True. No crossing starts below 4. sum(is_prime) counts both and is 2 too high. count_primes(10) returns 6 instead of 4.
Table of n + 1 slots. Count Primes (LC 204) counts primes strictly below n. The extra slot for n is never crossed, so a non-prime n is counted. count_primes(10) returns 5.
range(2, int(n ** 0.5)) without + 1. p never reaches the integer square root. For n = 10, 9 is not crossed and the answer is 5.
Crossing from 2 * p. The answer is correct, but the code writes to the same slots again. For n = 100, it makes 111 writes instead of 102.
A sieve for one number. Building a table of n slots to test one x costs more than trial division up to sqrt(x).

Practice

Canonical LeetCode:Count Primes (LC 204)Prime Arrangements (LC 1175)Prime Subtraction Operation (LC 2601)Prime Pairs With Target Sum (LC 2761)

Count Primes (LC 204)(opens leetcode.com)

Sieve of Eratosthenes

See it run

Deep Dive

Why crossing out multiples finds every prime

Why the crossing starts at p * p and p stops at the square root

Trace for n = 30: 10 primes below 30

Cost: O(n log log n) time and O(n) space

60-Second Pitch

Common Questions

SWE Reasoning

Spot it

The invariant, step by step

Traps

Practice

Count Primes (LC 204)(opens leetcode.com)

Sieve of Eratosthenes

See it run

Deep Dive

Why crossing out multiples finds every prime

Why the crossing starts at p * p and p stops at the square root

Trace for n = 30: 10 primes below 30

Cost: O(n log log n) time and O(n) space

60-Second Pitch

Common Questions

SWE Reasoning

Spot it

The invariant, step by step

Traps

Practice

Count Primes (LC 204)(opens leetcode.com)

Sieve of Eratosthenes

See it run

Deep Dive

Why crossing out multiples finds every prime

Why the crossing starts at p * p and p stops at the square root

Trace for n = 30: 10 primes below 30

Cost: O(n log log n) time and O(n) space

60-Second Pitch

Common Questions

SWE Reasoning

Spot it

The invariant, step by step

Traps

Practice

Count Primes (LC 204)(opens leetcode.com)

Sieve of Eratosthenes

See it run

Deep Dive

Why crossing out multiples finds every prime

Why the crossing starts at p * p and p stops at the square root

Trace for n = 30: 10 primes below 30

Cost: O(n log log n) time and O(n) space

60-Second Pitch

Common Questions

SWE Reasoning

Spot it

The invariant, step by step

Traps

Practice

Cost: O(n log log n) time and `O(n)` space

Cost: O(n log log n) time and `O(n)` space

Cost: O(n log log n) time and `O(n)` space

Cost: O(n log log n) time and `O(n)` space