Sieve of Eratosthenes

Find all primes up to $n$ by crossing out multiples — $O(n\log\log n)$.

Easy

is_p = [True] * (n + 1); is_p[0:2] = [False, False]
for i in range(2, int(n**0.5) + 1):
    if is_p[i]: is_p[i*i::i] = [False] * len(is_p[i*i::i])

Spotted a mistake or want to add detail? Suggest an improvement — Content Contributors' edits are reviewed by editors before they go live.

Discussion (0)