[ create a new paste ] login | about

Link: http://codepad.org/4tmWpcJF    [ raw code | output | fork ]

gre - Python, pasted on Feb 25:
#!/usr/bin/env python


def _drop_mults(xs):
    for i in xrange(0, len(xs), xs[0]):
        xs[i] = 0
    return filter(None, xs)


def euler(n):
    xs = range(3, n, 2)
    ps = [2]
    while xs:
        p = xs[0]
        ps.append(p)
        xs = _drop_mults(xs)
    return ps


# from Python Cookbook
from itertools import count, islice


def erat2():
    D = {}
    yield 2
    for q in islice(count(3), 0, None, 2):
        p = D.pop(q, None)
        if p is None:
            D[q * q] = q
            yield q
        else:
            x = p + q
            while x in D or not (x & 1):
                x += p
            D[x] = p


# Make a list using erat2()
def erat(n):
    ps = []
    e = erat2()
    p = e.next()
    while p <= n:
        ps.append(p)
        p = e.next()
    return ps


if __name__ == "__main__":
    import time

    def time_method(method, n):
        start = time.time()
        ps = method(n)
        stop = time.time()
        return "%e" % (stop - start)

    for method in [euler, erat]:
        print method.func_name
        print time_method(method, int(1e5))
        print "\n"


Output:
1
2
3
4
5
6
7
8
euler
2.523233e+00


erat
1.833749e-01




Create a new paste based on this one


Comments: