Sieve of Eratosthenes
Given n, return every prime number less than or equal to n.
Intuition
Testing each number for primality separately costs O(sqrt n) per number, so printing all primes up to n is O(n sqrt n) — far too slow at n = 10^6. The cost is in re-deriving, for each candidate, facts we already know. Turn it around: instead of asking each number whether it is prime, let each prime announce its own multiples as composite. Start with everything marked prime, walk upward, and whenever you meet a number that is still marked, it is prime — so cross out all of its multiples. What is left standing at the end is exactly the primes.
Cross out multiples rather than testing each number for primality. Two optimisations make it fast: stop the outer loop at √n, and start crossing at i * i because every smaller multiple of i already carries a smaller prime factor. Total work is O(n log log n).
Approach
Name the brute force and its cost
The straightforward answer loops i from 2 to n and calls an isPrime(i) helper that trial-divides up to sqrt(i). That is O(n sqrt n) overall. At n = 10^5 it is already sluggish; at 10^6 it is hopeless. The bottleneck is the primality check, so the goal is to make that check O(1).
Precompute a lookup table instead of testing
Allocate a boolean array of size n + 1 and initialise every entry to 'prime'. Immediately clear indices 0 and 1, since neither is prime by definition. Now the check prime[i] is a single array read — O(1). The entire question becomes how to fill this array cheaply.
Let each prime cross out its own multiples
Walk i upward from 2. Take n = 30. prime[2] is still set, so 2 is prime — and every multiple of 2 (4, 6, 8, ... 30) has 2 as a factor, so it cannot be prime. Clear them all. Move to 3: still set, so prime; clear 6, 9, 12, ... 30. Move to 4: it is already cleared, which tells us 2 divides it — and every multiple of 4 is also a multiple of 2 and has therefore already been cleared. So a cleared number needs no work at all. Skip it. That skip is what keeps the algorithm fast.
Two bounds that cut the work further
First, the inner loop can start at i i rather than 2 i. Any smaller multiple i k with k < i has a factor smaller than i and was cleared during that smaller factor's pass. Second, the outer loop only needs to run while i i <= n: past that point every remaining composite would need a factor above sqrt(n) paired with one below it, and the one below already struck it. Together these bring the total to O(n log log n).
Solution & live demo
Common pitfalls
Starting the inner loop at 2 * i
for j in range(2 * i, n + 1, i):
for j in range(i * i, n + 1, i):
Any multiple k i with k < i was already crossed out when the sieve processed k's smallest prime factor. Starting at i i skips that repeated work without missing a single composite.
Running the outer loop to n
for i in range(2, n + 1):
while i * i <= n:
A composite below n has a factor at most √n, so once i passes that point nothing new gets crossed. Continuing costs a full extra pass over the array for no effect.
Not excluding 0 and 1
prime = [1] * (n + 1)
prime[0] = 0 prime[1] = 0
Neither is prime, but neither is ever crossed out by the sieve — they have no multiples in range to trigger it. They must be cleared explicitly or they appear in the output.
Edge cases
There are no primes; the array is entirely cleared by the explicit prime[0] = prime[1] = 0 step and the loops never execute, so an empty list is returned.
The outer loop condition i * i <= n fails immediately at i = 2, nothing is crossed out, and 2 is correctly reported as prime.
Build the sieve once and reuse it. This is the real reason to prefer it over repeated isPrime calls — after the O(n log log n) setup, every subsequent primality question costs O(1).