Finding Prime Numbers Using Sieve of Eratosthenes in Python

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.