Prime Numbers

Extra · SVG · Sieveis_prime · Sieve of Eratosthenes · math

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.

Step 1 / 1
READY
Slides
Extra space
Window
Result
Codeis_prime
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

Examples

Sieve · LeetCode 204

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".

O(n log log n) timeO(n) spacetesting each number with is_prime would be O(n √n)
Sieve + scan · LeetCode 2523

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].

O(n log log n) timeO(n) spaceone sieve, then one pass

Time and space

MethodTimeSpaceWhy
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 nO(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 nO(n √n)O(1)Fine for one number, wasteful for many: that is when to sieve.

Why start crossing at i × i?

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.

Where it connects

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.

Trigger words

One number

  • is n prime

Trial division up to √n.

Many numbers

  • count primes less than n
  • all primes up to n

Sieve once, then read the flags.

Template

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]