Accelerating the Sieve of Eratosthenes1. Quickly recall the algorithm
Classic implementation:
def eratosthenes(n):
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False
for i in range(2, int(n ** 0.5) + 1):
if is_prime[i]:
for j in range(i * i, n + 1, i):
is_prime[j] = False
return is_prime
Time — O(N log log N). We're not interested in the asymptotics, but in how much we can speed up the implementation itself.
2. Optimization #1 — don't bother with even numbers
The idea is simple:
* all even numbers except 2 are composite
* if we only work with odd numbers, we reduce the array size and the number of iterations by about half
Implementation:
def eratosthenes_odd(n):
if n < 2:
return []
size = (n + 1) // 2
is_prime = [True] * size
is_prime[0] = False
limit = int(n ** 0.5) // 2
for i in range(1, limit + 1):
if is_prime[i]:
p = 2 * i + 1
start = (p * p) // 2
for j in range(start, size, p):
is_prime[j] = False
return is_prime
3. Optimization #2 — use bytearray instead of list[bool]
Thought:
* bool in Python is an object
* bytearray is a tightly packed buffer
* less overhead and better fits into the CPU cache
Example:
def eratosthenes_bytearray(n):
is_prime = bytearray(b"\x01") * (n + 1)
is_prime[0:2] = b"\x00\x00"
for i in range(2, int(n ** 0.5) + 1):
if is_prime[i]:
for j in range(i * i, n + 1, i):
is_prime[j] = 0
return is_prime
4. Optimization #3 — a hybrid of the two approaches
def eratosthenes_fast(n):
if n < 2:
return []
size = (n + 1) // 2
is_prime = bytearray(b"\x01") * size
is_prime[0] = 0
limit = int(n ** 0.5) // 2
for i in range(1, limit + 1):
if is_prime[i]:
p = 2 * i + 1
start = (p * p) // 2
is_prime[start::p] = b"\x00" * (((size - start - 1) // p) + 1)
return is_prime
5. Time comparison
Test with
n = 10_000_000:
>>> eratosthenes.py
real 0.634s
>>> eratosthenes_odd.py
real 0.245s
>>> eratosthenes_bytearray.py
real 0.801s
>>> eratosthenes_fast.py
real 0.028sConclusions:
* skipping even numbers (#1) gives ~2.6× speedup
* bytearray itself doesn't speed up — it's more about memory
* the hybrid (#3) gives ~22.6× speedup
Key trick in #3:
is_prime[start::p] = b"\x00" * (((size - start - 1) // p) + 1)
There's no Python loop here — everything is done by a C-level operation on the slice. On such tasks, this makes a huge difference.
General idea: in Python, we often speed up not the asymptotics, but the memory model and the number of passes over the data. Loops + memory → the main factors.
👉
@DataScience4 
