3. Sieve of Eratosthenes

VCMNA221: level 6: Design algorithms involving branching and iteration to solve specific classes of mathematical problems

  • implementing algorithms such as the Euclidean division algorithm

This Python code snippet uses iteration to implement the Sieve of Eratosthenes algorithm to find all prime numbers below 100.
../_images/Sieve_of_Eratosthenes.png

3.1. Sieve_v1: Primes below 100

This code creates a list of boolean values representing the numbers from 0 to n (in this case, n is 100).
It then iterates over the list, starting from the first prime number p (2), and marks all multiples of p as not prime.
This process is repeated for all numbers until p squared is greater than n.
Finally, the code iterates over the list of boolean values and appends the index of each True value to a list of prime numbers.
The resulting list of prime numbers is then printed.
"""implement the Sieve of Eratosthenes algorithm to find all prime numbers below 100
"""

def sieve_of_eratosthenes(n):
    # Define a function to generate primes using the Sieve of Eratosthenes algorithm
    prime = [True for i in range(n + 1)]
    p = 2
    while p * p <= n:
        if prime[p]:
            for i in range(p * p, n + 1, p):
                prime[i] = False
        p += 1

    primes = []
    for p in range(2, n):
        if prime[p]:
            primes.append(p)
    return primes
        
n = 100
print(sieve_of_eratosthenes(n))
The output is: [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]

3.2. Sieve_v2: Primes below 100

This can be improved such that p is incremented until the next lowest prime is found.
In this version of the code, after marking all multiples of p as not prime, we enter a while loop that increments p until a True value is found.
This ensures that we only consider prime numbers as potential values for p.
 1"""implement the Sieve of Eratosthenes algorithm to find all prime numbers below 100
 2"""
 3
 4
 5def sieve_of_eratosthenes(n):
 6    # Define a function to generate primes using the Sieve of Eratosthenes algorithm
 7    prime = [True for i in range(n + 1)]
 8    p = 2
 9    while p * p <= n:
10        if prime[p]:
11            for i in range(p * p, n + 1, p):
12                prime[i] = False
13        p += 1
14        while not prime[p]:
15            p += 1
16
17    primes = []
18    for p in range(2, n):
19        if prime[p]:
20            primes.append(p)
21    return primes
22
23
24n = 100
25print(sieve_of_eratosthenes(n))
The output is: [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]

3.3. Sieve_v3: Primes below 100

SLightly different python techniques can be used as illustrated in this code that uses list multiplication, for-loops and list comprehension.
 1"""implement the Sieve of Eratosthenes algorithm to find all prime numbers below 100
 2"""
 3import math
 4
 5def sieve_of_eratosthenes(n):
 6    # Define a function to generate primes using the Sieve of Eratosthenes algorithm
 7    # Create a boolean array of size n+1, initialized to True
 8    is_prime = [True] * (n+1)
 9    # Mark 0 and 1 as not prime
10    is_prime[0] = is_prime[1] = False
11    # Iterate over the numbers from 2 to the square root of n
12    for i in range(2, int(math.sqrt(n)) + 1):
13        # If i is prime, mark all its multiples as not prime
14        if is_prime[i]:
15            for j in range(i*i, n+1, i):
16                is_prime[j] = False
17    # Return a list of primes by filtering the array
18    return [i for i in range(2, n+1) if is_prime[i]]
19
20
21# Define the upper limit of the range
22n = 100
23# Generate the primes using the sieve function
24primes = sieve_of_eratosthenes(n)
25print(primes)
The output is: [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]