Eratosthene sieve

primes.py

#!/usr/bin/env pypy
#-*- coding: utf-8 -*-

def get_primes(n=10**6):
    if n < 2:
        return []

    sieve = [True] * (n + 1)
    sieve[:2] = [False, False]
    #primes = [2]
    m = int(n ** .5) + 1

    for i in xrange(3, m, 2):
        if sieve[i]:
            #primes.append(i)
            for j in xrange(i, n // i + 1, 2):
                sieve[i * j] = False

    return sieve
    #if m % 2 == 0:
    #    m += 1

    #for i in xrange(m, n + 1, 2):
    #    if sieve[i]:
    #        primes.append(i)

    #return primes

if __name__ == '__main__':
    get_primes(10 ** 9)