"""
 sieve.py

 Implement sieve of Eratoshenes to find prime numbers.

 This is exercise 10 from chapter 11 of Zelle,
 and a class algorithm dating back to ancient Greek times.

 See https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
 for an explanation and example.


    $ python sieve.py
    -- find prime numbers up to n --
    What is n? (100) 100
    The primes are
    [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 
    53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

 Tested with python 3.9.

 Jim Mahoney | cs.bennington.college | MIT License | April 2021
"""

def set_multiples_to_zero(numbers, i):
    """ modify numbers in place by setting multiples of i to 0 """
    # We want to set numbers[2*i], numbers[3*i], etc to 0.
    multiple = 2*i   # this is the first one 
    while multiple < len(numbers):      # loop while we're within the list
        numbers[multiple] = 0
        multiple = multiple + i

def get_nonzero(numbers):
    """ return a list of the elements of numbers which are not zero """
    primes = []
    for number in numbers:
        if number != 0:
            primes.append(number)
    return primes

def main():
    print("-- find prime numbers up to n --")
    n = int(input("What is n? (100) "))

    # First create a list off all the numbers which might be prime,
    # from 0 up to n. (I keep 0 in the lst so that numbers[i] is i,
    # which makes it simple to know which is where.)
    numbers = list(range(n+1))    # [0, 1, 2, 3, 4, ... , n]

    # I will change anything which is not prime to 0
    # and at the end print all non-zero ones.

    # Start by marking 1 as not prime.
    numbers[1] = 0       
    
    # Loop over all the possible primes in the list,
    # starting from 2. For each of those, mark it
    # as not prime by setting it to zero.
    for i in range(2, n+1):
        if numbers[i] != 0:
            set_multiples_to_zero(numbers, i)

    # Then we just print out the ones that aren't zero.
    print("The primes are ")
    print(get_nonzero(numbers))
        
if __name__ == '__main__':
    main()