Drag across the numbers. Click it, then use ← → to step and Space to play.
A prime has no divisors besides 1 and itself; 2 is the only even prime. To test one number, you only need to try divisors up to its square root: if n = a × b, one of the two is at most √n. To find all primes up to n, the Sieve of Eratosthenes works the other way round: assume everything is prime, then cross out the multiples of each prime you find, starting from its square.
FIG. E · Numbers drawn as tiles. In is_prime, the candidate divisors line up with i × i written underneath, and the ones past √n are faded because the loop never reaches them. In the sieve, 0 to n are laid out in rows of ten: red is the prime doing the crossing, slashed tiles are composites, and inked tiles are the primes that survive.
def is_prime(n):
if n < 2:
return False
i = 2
while i * i <= n:
if n % i == 0:
return False
i += 1
return True
def primes_up_to(n): # Sieve of Eratosthenes
if n < 2:
return []
is_p = [True] * (n + 1)
is_p[0] = is_p[1] = False
for i in range(2, int(n ** 0.5) + 1):
if is_p[i]:
for j in range(i * i, n + 1, i):
is_p[j] = False
return [i for i, p in enumerate(is_p) if p]
def countPrimes(n): # LeetCode 204: primes < n
if n < 3:
return 0
is_p = [True] * n
is_p[0] = is_p[1] = False
for i in range(2, int(n ** 0.5) + 1):
if is_p[i]:
for j in range(i * i, n, i):
is_p[j] = False
return sum(is_p)
def closestPrimes(left, right): # LeetCode 2523
is_p = sieve(right) # the is_p list from primes_up_to
ps = [p for p in range(left, right + 1) if is_p[p]]
best = [-1, -1]
for a, b in zip(ps, ps[1:]):
if best[0] == -1 or b - a < best[1] - best[0]:
best = [a, b]
return best
How many primes are less than 20? Sieve 0..19 and count what survives: 2, 3, 5, 7, 11, 13, 17, 19. Answer: 8. Trigger: "count primes less than n".
left = 10, right = 19. Sieve up to 19, list the primes in range (11, 13, 17, 19) and keep the neighbouring pair with the smallest gap. Answer: [11, 13].
| Method | Time | Space | Why |
|---|---|---|---|
| is_prime(n) | O(√n) | O(1) | Divisors come in pairs a × b = n with a ≤ √n, so checking up to √n is enough. |
| Sieve up to n | O(n log log n) | O(n) | Each prime p crosses out about n/p numbers; n/2 + n/3 + n/5 + … ≈ n log log n. |
| is_prime on every number up to n | O(n √n) | O(1) | Fine for one number, wasteful for many: that is when to sieve. |
Every smaller multiple of i, like 2i or 3i, has a smaller factor (2, 3, …) and was already crossed out when that smaller prime ran. So the first multiple of i that is still standing is i × i. The same fact is why the outer loop can stop at √n.
The sieve is an array of flags indexed by number, like the counts array of bucket sort (page 4) or the visit set of a graph (page 10). is_prime is a loop with an early exit, like a linear search that stops at √n.
Trial division up to √n.
Sieve once, then read the flags.
def is_prime(n):
if n < 2:
return False
i = 2
while i * i <= n:
if n % i == 0:
return False
i += 1
return True
def primes_up_to(n): # Sieve of Eratosthenes
if n < 2:
return []
is_p = [True] * (n + 1)
is_p[0] = is_p[1] = False
for i in range(2, int(n ** 0.5) + 1):
if is_p[i]:
for j in range(i * i, n + 1, i):
is_p[j] = False
return [i for i, p in enumerate(is_p) if p]