Implementation of Sieve of Eratosthenes in Python

primes.py

# This file is in the public domain.


class MyNumber(int):

    def __init__(self, x=0, base=10):
        super(int, self).__init__()
        self.marked = False


def sieve_of_eratosthenes(bottom, top=None):
    if top is None:
        top = bottom
        bottom = 2

    bottom = max(bottom, 2)

    sieve = [MyNumber(x) for x in range(bottom, top + 1)]
    p = 2
    while p is not None:
        sieve, p = wittle_sieve(sieve, p)

    return [x for x in sieve if not x.marked]


def wittle_sieve(sieve, p):
    next_p = None
    for idx, val in enumerate(sieve):
        if val != p and val % p == 0:
            sieve[idx].marked = True
        elif sieve[idx].marked is False and p < val and next_p is None:
             next_p = val
    return (sieve, next_p)


# Somewhat faster implementation using set and frozenset.


def faster_sieve_of_eratosthenes(bottom, top=None):
    if top is None:
        top = bottom
        bottom = 2

    bottom = max(bottom, 2)

    sieve = set(xrange(bottom, top + 1))
    p = 2
    while p is not None:
        sieve, p = faster_wittle_sieve(sieve, p)

    return sieve


def faster_wittle_sieve(sieve, p):
    next_p = None
    for n in frozenset(sieve):
        if n != p and n % p == 0:
            sieve.remove(n)
        elif p < n and next_p is None:
             next_p = n
    return (sieve, next_p)


if __name__ == '__main__':
    import sys
    print(faster_sieve_of_eratosthenes(int(sys.argv[1]), int(sys.argv[2])))