Prime Sieve

In [1]:

import time

In [2]:

_sieve_limit = 1000000
_sqrt_limit = int(_sieve_limit**0.5)+1

isPrime = [True] * _sieve_limit

In [3]:

# warning: 
# isPrime[0] = True
# isPrime[1] = True

In [4]:

t=time.time()

for x in range(2, _sqrt_limit):
    if isPrime[x]: 
        for i in range(x*x, _sieve_limit, x):
            isPrime[i] = False

print(time.time()-t)

1.0842921733856201

In [5]:

# sum of all primes below 1,000,000

print(sum(i for i in range(2, _sieve_limit) if isPrime[i]))

37550402023

In [6]:

# find the 10001st prime

counter = 0
for x in range(2, _sieve_limit):
    if isPrime[x]:
        counter += 1
        if counter==10001:
            print(counter, x)
            break

10001 104743