sieve.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def sieve(limit):
    # Start off assuming everything is prime (True)

    # Start with some "special cases":
    # 0 included for convenience and is not prime
    # 1 is not prime
    # 2 is prime but special case as it's the only even prime
    # Then mark all even numbers as prime - there's only one (2)
    table = (
        [False, False, True][:limit+1] +
        [(i % 2 != 0) for i in xrange(3, limit+1)]
    )

    # Start at 3 and iterate through the table 2 at a time
    limit_sqrt = int(limit**0.5) + 1
    for i in xrange(3, limit_sqrt, 2):
        if table[i]:
            # Found the next prime... mark all its multiples as non-prime
            # (not including itself)
            for j in xrange(i*i, limit+1, i):
                table[j] = False

    return [i for i, is_prime in enumerate(table) if is_prime]

Comments

Made it work for 0 and 1 cases. (it was erroneously including 2)

helenst commented 15 March 2016 at 09:10 UTC

You're not logged in right now. Please login via GitHub to comment