Bits of Discovery

Stuff I Like to Learn About

Sieve of Eratosthenes

So I’ve been taking an interest in prime numbers recently and how to generate them, so I wrote a up a quick implementation of The Sieve of Eratosthenes in Python. Here it is:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

def primes(n):
  candidates = []
  for i in range(2, n+1):
    candidates.append([i, False])
  p = 2
  sieve(candidates, p)

def sieve(candidates, p):
  done = False
  while(not done):
    for pair in candidates[p-2::p][1:]:
      pair[1] = True

    found = False
    rest = candidates[(p-2):][1:]
    for pair in rest:
      if not pair[1]:
        p = pair[0]
        found = True
        break

    if not found:
      done = True

  for pair in candidates:
    if not pair[1]:
      print pair[0]

For those interested in more curious facts about prime numbers a brilliant talk is given by the great Terrence Tao. It’s a bit lengthy but well worth your time.