import math
import time

LENGTH = 1000000/2+1

elapsed = 0

data = [True]*LENGTH
data[0] = False;
i = 1   #spot in the list (data)
m = 1   #multiple: starts at 2, then increments in by 1
n = 0   #number (n = 2*i + 1)
sqrt_of_length = math.sqrt(LENGTH)

print 2*LENGTH  #(length-1)*2+1

start = time.clock()

while i < sqrt_of_length:
    if data[i] == True:
        n = 2*i + 1
        spot = n
        while spot < LENGTH:
            data[spot] = False
            spot += n
    i += 1
    m = 1

end = time.clock()

elapsed = end - start

print "It took", elapsed, "seconds to build the sieve"


## prints out all the numbers
##i = 0;
##data.sort()
##while i < len(data):
##    if data[i] == 0:
##        del data[i];
##    i += 1
##print data