2015-07-01

Eratosthenes Sieve

I have been researched python version of Eratosthenes Sieve. Below snippet is simple but fast enough.

I just fixed comments and values of snippet from below link.

エラトステネスの篩（Python編）

# -*- coding: utf-8 -*-
import math

def sieve(n):
    # initialize 2, 3, 5 primes and those multiple values remove
    blist = [False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else True for i in range(n)]
    blist[0] = blist[1] = False
    blist[2] = blist[3] = blist[5] = True
    sqrt = math.sqrt(n)

    for odd in range(7, n, 2):  # odd number above prime value 7
        if odd >= sqrt: # Eratosthenes Step 3
            return [i for i, b in enumerate(blist) if b is True]

        for s in range(odd ** 2, n, odd):  # start from square value, pick multiple odd value
            blist[s] = False

if __name__ == '__main__':
    n = 2000000  # 2 million primes
    plist = sieve(n)
    print(len(plist))
    print(sum(plist))