benchmark.py

#!/usr/bin/
# -*- encoding:utf-8 -*-

from itertools import count, islice, takewhile, imap
import time

def primes1(candidates = count(2)):
    # Pick a prime and yield.
    prime = candidates.next()
    yield prime

    # Yield primes after it, which are not
    # divided by it.
    nextprimes = (n for n in primes1(candidates) if n % prime)
    while True: yield nextprimes.next()

def primes2():
    primes = []
    for n in count(2):
        # To be fare, do not optimize
        # div_cand = takewhile(lambda x: x ** 2 <= n, primes)
        has_div = any(imap(lambda x: n % x == 0, primes))
        if not has_div:
            primes.append(n)
            yield n

def measure_time(f):
    def decorate(*args, **kwargs):
        starts = time.time()
        res = f(*args, **kwargs)
        print '%.2f' % ((time.time() - starts) * 1000,)
        return res

    return decorate

@measure_time
def take(iterator, n):
    return list(islice(iterator, 0, n))

# print first 10 primes.
print take(primes1(), 40)
print take(primes2(), 40)

benchmark_result.txt

5.19
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173]
0.24
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173]

sieve_of_eratosthenes.py

#!/usr/bin/env python
# -*- encoding:utf-8 -*-

from itertools import count, islice

def primes(candidates = count(2)):
    # Pick a prime and yield.
    prime = candidates.next()
    yield prime

    # Yield primes after it, which are not
    # divided by it.
    nextprimes = (n for n in primes(candidates) if n % prime)
    while True: yield nextprimes.next()

def take(iterator, n):
    return list(islice(iterator, 0, n))

# print first 10 primes.
print take(primes(), 10)

뭐, 처음 보면 neat하고 엄청 효율적일 거 같아 보이긴 해도, 결국 approximately O(n lg lg n)의 time complexity를 가지는 건 똑같다. 오히려 prime 개수만큼 generator를 유지해야 하니까 간단한 형태의 구현이 더 빠르다.