from math import *

def sieve(n):
    primes = [True] * (n+1)                             # true for each primes
    primes[0] = primes[1] = False
    for i in range(2, int(sqrt(n))+1):                  # filter out non-primes
        if primes[i]:
            for j in range(i**2, n+1, i):
                primes[j] = False
    return [i for i in range(len(primes)) if primes[i]] # generate primes from True values
 
primes = sieve(1000000)