from time import time
 
def primes(n): # sieve of eratosthenes
    i, p, ps, m = 0, 3, [2], n // 2
    sieve = [True] * m
    while p <= n:
        if sieve[i]:
            ps.append(p)
            for j in range((p*p-3)/2, m, p):
                sieve[j] = False
        i, p = i+1, p+2
    return ps
 
start = time()
print len(primes(1000000))
print time() - start
 
def isPrime(n): # trial division
	if n % 2 == 0: return n == 2
	d = 3
	while d * d <= n:
		if n % d == 0: return False
		d += 2
	return True
 
start = time()
ps = []
 
for p in range(2,1000000):
	if isPrime(p):
		ps.append(p)
 
print len(ps)
print time() - start# your code goes here

ZnJvbSB0aW1lIGltcG9ydCB0aW1lCgpkZWYgcHJpbWVzKG4pOiAjIHNpZXZlIG9mIGVyYXRvc3RoZW5lcwogICAgaSwgcCwgcHMsIG0gPSAwLCAzLCBbMl0sIG4gLy8gMgogICAgc2lldmUgPSBbVHJ1ZV0gKiBtCiAgICB3aGlsZSBwIDw9IG46CiAgICAgICAgaWYgc2lldmVbaV06CiAgICAgICAgICAgIHBzLmFwcGVuZChwKQogICAgICAgICAgICBmb3IgaiBpbiByYW5nZSgocCpwLTMpLzIsIG0sIHApOgogICAgICAgICAgICAgICAgc2lldmVbal0gPSBGYWxzZQogICAgICAgIGksIHAgPSBpKzEsIHArMgogICAgcmV0dXJuIHBzCgpzdGFydCA9IHRpbWUoKQpwcmludCBsZW4ocHJpbWVzKDEwMDAwMDApKQpwcmludCB0aW1lKCkgLSBzdGFydAoKZGVmIGlzUHJpbWUobik6ICMgdHJpYWwgZGl2aXNpb24KCWlmIG4gJSAyID09IDA6IHJldHVybiBuID09IDIKCWQgPSAzCgl3aGlsZSBkICogZCA8PSBuOgoJCWlmIG4gJSBkID09IDA6IHJldHVybiBGYWxzZQoJCWQgKz0gMgoJcmV0dXJuIFRydWUKCnN0YXJ0ID0gdGltZSgpCnBzID0gW10KCmZvciBwIGluIHJhbmdlKDIsMTAwMDAwMCk6CglpZiBpc1ByaW1lKHApOgoJCXBzLmFwcGVuZChwKQoKcHJpbnQgbGVuKHBzKQpwcmludCB0aW1lKCkgLSBzdGFydCMgeW91ciBjb2RlIGdvZXMgaGVyZQ==