ECX 30 Days of Code and Design

Day 23

Sieve of Eratosthenes

Task

The sieve of Eratosthenes is an ancient algorithm for finding all primes less than a given value N. It operates as follows:

1. Create a list of consecutive integers from 2 through n: (2, 3, 4, ..., n)

2. Initially, let p equal 2, the smallest prime number

3. Enumerate the multiples of p by counting in increments of p from 2p to n, and mark them in the list (these will be 2p, 3p, 4p, …; the p itself should not be marked)

4. Find the smallest number in the list greater than p that is not marked. If there was no such number, stop. Otherwise, let p now equal this new number (which is the next prime), and repeat from step 3

5. When the algorithm terminates, the numbers remaining not marked in the list are all the primes below n See more: Sieve of Eratosthenes.

Using the Sieve of Eratosthenes (as described above), Write a function that takes in an integer as input, and returns a list containing all primes less than that input number.

My Approach

Below is the full code. It would be explained in bits throughout this article.

def sieve_of_eratosthenes(user_input):
    """Prints out prime numbers below the argument inputted"""
    list_of_composite = []              # To store composite numbers
    list_of_prime = []                  # To store prime numbers

    prime_num = 2                       # Starting from the first prime number
    multiplier = 2                      # To get the multiples of the prime number
    multiples = 0                       # Store the values of multiples of prime numbers

    while prime_num < user_input:

        if prime_num in list_of_composite:
            prime_num += 1
            continue

        else:
            list_of_prime.append(prime_num)

            # Finding multiples of prime numbers and storing them in composite list
            while multiples < user_input:
                multiples = prime_num * multiplier

                # Prevent inputting the same number in composite list
                if multiples in list_of_composite:
                    multiplier += 1
                    continue

                # Input multiples of prime not yet in the composite list
                else:
                    list_of_composite.append(multiples)
                multiplier += 1

            # Reverts the multiplier and multiples variable to zero to prime number to a new number
            multiples = 0
            multiplier = 2

        prime_num += 1
    print(list_of_prime)


print(' Find Prime Numbers Using Sieve of Eratosthenes '.center(50, '*'))
print('Find the prime numbers below a certain number.')

try:
    user_inputs = int(input('Enter number: '))

    # Function Call
    sieve_of_eratosthenes(user_inputs)
except ValueError:
    print('Invalid input! Enter only integers.')

First, we define the function, sieve_of_erastosthenes(), which would print out the prime numbers below the number inputted by the user. Next, we create a list which would contain the composite (non-prime) numbers, and another list which would contain the prime numbers. We then create variables; prime_num would have values 2 to (user input – 1). If it is found to be a prime number, it is added to list_of_prime, else it is added to list_of_composite; multiplier would be used to get the multiples of every prime number below the user input, while multiples stores the values, and is added to list_of_composite if it is not already in there.

def sieve_of_eratosthenes(user_input):

    list_of_composite = []
    list_of_prime = [] 

    prime_num = 2                    
    multiplier = 2                   
    multiples = 0

Next, using a while loop, we increase the variable, prime_num, from 2 to the (user’s input - 1). We check if the user input is already in list_of_composite; if yes, we increase its value and go to the start of the loop, else, we add the value to list_of_prime, after which we get it multiples below the user’s input and add them to list_of_composite. When we get all its multiples, we increase the value of prime_num. When the prime numbers below the user’s input have been gotten, the function prints out the list items of list_of_prime.

    while prime_num < user_input:

        if prime_num in list_of_composite:
            prime_num += 1
            continue

        else:
            list_of_prime.append(prime_num)

            while multiples < user_input:
                multiples = prime_num * multiplier

                if multiples in list_of_composite:
                    multiplier += 1
                    continue

                else:
                    list_of_composite.append(multiples)
                multiplier += 1

            multiples = 0
            multiplier = 2

        prime_num += 1
    print(list_of_prime)

Finally, we ask the user to input an integer and pass the input to the function, which prints out a list of prime numbers below the user’s input.

print(' Find Prime Numbers Using Sieve of Eratosthenes '.center(50, '*'))
print('Find the prime numbers below a certain number.')

try:
    user_inputs = int(input('Enter number: '))

    sieve_of_eratosthenes(user_inputs)
except ValueError:
    print('Invalid input! Enter only integers.')

Output

If a user inputs 100, s/he gets;

* Find Prime Numbers Using Sieve of Eratosthenes *
Find the prime numbers below a certain number.
Enter number: 100
[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]

Run the code on Replit.