cr_sieve_of_eratosthenes.py

from time import time


def SieveofEratosthenes(primeseries):

    i=1
    primeserieslist = []
    while(i<primeseries):
        i=i+1
        primeserieslist.append(i)

    x=2

    primeslist = []

    while x <= primeseries and x*2 <= primeseries:
        j=2
        while (j < primeseries):
            z = j*x
            if (z <= primeseries):
                if (z in primeserieslist):
                    primeserieslist.remove(z)
            j = j+1

        x=x+1
    return primeserieslist


def sieve_of_eratosthenes(max_integer):
    sieve = [True for _ in range(max_integer + 1)]
    sieve[0:1] = [False, False]
    for start in range(2, max_integer + 1):
        if sieve[start]:
            for i in range(2 * start, max_integer + 1, start):
                sieve[i] = False
    primes = []
    for i in range(2, max_integer + 1):
        if sieve[i]:
            primes.append(i)
    return primes


def millis():
    return int(round(time() * 1000))


if __name__ == "__main__":
    n = 10000
    start = millis()
    primes1 = SieveofEratosthenes(n)
    end = millis()
    print "SieveofEratosthenes in", end - start, "milliseconds."
    start = millis()
    primes2 = sieve_of_eratosthenes(n)
    end = millis()
    print "sieve_of_eratosthenes in", end - start, "milliseconds."
    print "Algorithms agree:", primes1 == primes2