# Commits

committed df94dda

• Participants
• Parent commits 58855bb

# File primes.py

`+"""Prime numbers`
`+"""`
`+`
`+`
`+import itertools`
`+`
`+`
`+def primes():`
`+  """Yield prime numbers using the Sieve of Eratosthenes`
`+`
`+  From: http://macdevcenter.com/pub/a/python/excerpt/pythonckbk_chap1/index1.html?page=2`
`+  Credit: David Eppstein, Tim Peters, Alex Martelli, Wim Stolker, Kazuo`
`+  Moriwaka, Hallvard Furuseth, Pierre Denis, Tobias Klausmann, David Lees,`
`+  Raymond Hettinger`
`+  """`
`+  D = {}  # map each composite integer to its first-found prime factor`
`+  for q in itertools.count(2):`
`+    p = D.pop(q, None)`
`+    if p is None:`
`+      # q not a key in D, so q is prime, therefore, yield it.`
`+      yield q`
`+      # Mark q squared as composite with q as first-found prime factor.`
`+      D[q * q] = q`
`+    else:`
`+      # Find the smallest multiple of p which isn't yet known to be`
`+      # composite.  Already known composites will be eliminated in turn,`
`+      # and their stored prime factors will be advanced at that time.`
`+      # We know q is a composite multiple of p, so start at p + q.`
`+      x = p + q`
`+      while x in D:`
`+        x += p`
`+      # Mark this previously unknown composite with p as a prime factor.`
`+      D[x] = p`
`+`
`+`
`+def twin_primes():`
`+  """Yield pairs of twin primes"""`
`+  it = iter(primes())`
`+  for prev in it: break`
`+  for x in it:`
`+    if prev + 2 == x:`
`+      yield (prev, x)`
`+    prev = x`