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