SIEVING

N = 1000025

sieve = [False for _ in range(N)]
primes = []

for i in range(2, N):
    if not sieve[i]:
        primes += [i]
    for p in primes:
        if i * p >= N:
            break
        sieve[i * p] = True
        if i % p == 0:
            break