sieve_of_eratosthenes.py

def sieve(n):
    ''' 
    find all primes less than n
    parameter: a natural number n
    return: array of length n
        the ith element is a binary flag that indicates if the natural number i is prime
        (1 for prime, 0 for composite)
    ''' 
    x = [1] * n
    x[1] = 0
    
    # from 2 to n/2 (non-inclusive)
    for i in range(2,int(n/2)):
            # start w/ double of i. next will be the triple, and so on
            j = 2 * i
            
            while j < n:
                # mark the multiple as composite. then increment by i
                x[j]=0 
                j = j+i
                    
    return x