from math import sqrt

def pri2(n):
    primes = []
    p = 2
    while p <= n:
        prime = True
	s = sqrt(p)
        for k in primes:
            if k > s:
                break
            if p % k == 0:
                prime = False
                break
        if prime:
            primes.append(p)
        p += 1

    return primes



def pri(n):
    primes = []
    p = 2
    while p <= n:
        prime = True
        for k in primes:
            if p % k == 0:
                prime = False
                break
        if prime:
            primes.append(p)
        p += 1

    return primes



''' Results:
In [66]: %time x=pri(100000)
CPU times: user 2.97 s, sys: 0.00 s, total: 2.97 s
Wall time: 2.97 s

In [67]: %time y=pri2(100000)
CPU times: user 0.17 s, sys: 0.00 s, total: 0.17 s
Wall time: 0.17 s

In [68]: x==y
Out[68]: True
'''