primes.py

#!/usr/bin/env python3
from itertools import islice
from time import time

def time_generator(func, n=500000):
  generator = func()
  start     = time()
  islice(generator, n)
  elapsed   = time() - start

  print("[%s] %0.9fs (%d iterations): " % (func.__name__, elapsed, n))

def prime_generator_pseudotest():
  """ Yields an infinite sequence of primes using a pseudo-prime testing trick """
  small_primes = (2, 3, 5, 7, 11)
  p = 2

  while True:
    if 0 not in (pow(w,p-1,p) == 1 for w in small_primes if p > w):
      yield p
    p += 1
    

def prime_generator():
  """ Yields an infinite sequence of primes using the Sieve of Eratosthenes. """
  D = {}  # map composite integers to primes witnessing their compositeness
  q = 2   # first integer to test for primality
  while 1:
    if q not in D:
      yield q        # not marked composite, must be prime
      D[q*q] = [q]   # first multiple of q not already marked

    else:
      for p in D[q]: # move each witness to its next multiple
        D.setdefault(p+q,[]).append(p)
      del D[q]       # no longer need D[q], free memory

    q += 1


a = list(islice(prime_generator(), 100000))
b = list(islice(prime_generator_pseudotest(), 100000))
only_b = set(b) - set(a)
only_a = set(a) - set(b)
print("only pg:", sorted(only_a))
print("only pg_pt", sorted(only_b))

# time_generator(prime_generator)
# time_generator(prime_generator_pseudotest)