Python Math: Print all primes (Sieve of Eratosthenes) smaller than or equal to a specified number

Last update on April 02 2025 12:28:58 (UTC/GMT +8 hours)

21. Sieve of Eratosthenes

Write a Python program to print all primes (Sieve of Eratosthenes) smaller than or equal to a specified number.

In mathematics, the sieve of Eratosthenes, one of a number of prime number sieves, is a simple, ancient algorithm for finding all prime numbers up to any given limit. It does so by iteratively marking as composite (i.e., not prime) the multiples of each prime, starting with the multiples of 2.

Pictorial presentation:

Animation Credits: Author information here

Sample Solution:

Python Code:

def sieve_of_Eratosthenes(num):
    limitn = num+1
    not_prime_num = set()
    prime_nums = []

    for i in range(2, limitn):
        if i in not_prime_num:
            continue

        for f in range(i*2, limitn, i):
            not_prime_num.add(f)

        prime_nums.append(i)

    return prime_nums

print(sieve_of_Eratosthenes(100));

Sample Output:

[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]

Flowchart:

For more Practice: Solve these Related Problems:

• Write a Python program to print all prime numbers up to a specified limit using the Sieve of Eratosthenes algorithm.
• Write a Python function that returns a list of prime numbers below a given number and prints the total count of primes found.
• Write a Python script to implement the Sieve of Eratosthenes and then output the prime numbers in a formatted column layout.
• Write a Python program to optimize the Sieve of Eratosthenes for large limits and measure the time taken for execution.

Python Code Editor:

Have another way to solve this solution? Contribute your code (and comments) through Disqus.

Previous: Write a Python program to calculate magic square.
Next: Write a python program to find the next smallest palindrome of a specified number.