gistfile1.py

from math import sqrt

# straightforward
def pri1(n):
    primes = []

    for p in xrange(2,n+1):
        for k in primes:
            if p % k == 0:
                break
        else:
            primes.append(p)

    return primes


# optimized?
def pri2(n):
    primes = [2]

    for p in xrange(3,n+1,2):
        prime = True
        s = int(sqrt(p))
        for k in primes:
            if k > s:
                break
            if not p % k:
                prime = False
                break
        if prime:
            primes.append(p)

    return primes


# pri1(100*1000)
# CPU times: user 3.13 s, sys: 0.00 s, total: 3.13 s

# pri2(100*1000)
# CPU times: user 0.16 s, sys: 0.00 s, total: 0.16 s


# pri1(1000*1000)
# CPU times: user 203.19 s, sys: 0.00 s, total: 203.19 s

# pri2(1000*1000)
# CPU times: user 2.42 s, sys: 0.00 s, total: 2.42 s


# pri1(10*1000*1000)
# CPU times: user 14753.86 s, sys: 0.00 s, total: 14753.86 s

# pri2(10*1000*1000)
# CPU times: user 42.42 s, sys: 0.00 s, total: 42.42 s