Commits

Roger Pate committed df94dda

Add primes.py

Comments (0)

Files changed (1)

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