w3resource

Python: Sieve of Eratosthenes method, for computing prime number

Python List: Exercise - 34 with Solution

Write a Python program using Sieve of Eratosthenes method for computing primes upto a specified number.

Note: In mathematics, the sieve of Eratosthenes (Ancient Greek: κόσκινον Ἐρατοσθένους, kóskinon Eratosthénous), one of a number of prime number sieves, is a simple, ancient algorithm for finding all prime numbers up to any given limit.

Python: Sieve of Eratosthenes method, for computing prime number

From Wikipedia Sieve of Eratosthenes: algorithm steps for primes below 121 (including optimization of starting from prime's square).

Sample Solution:-

Python Code:

def prime_eratosthenes(n):
    prime_list = []
    for i in range(2, n+1):
        if i not in prime_list:
            print (i)
            for j in range(i*i, n+1, i):
                prime_list.append(j)

print(prime_eratosthenes(100));

Sample Output:

2                                                                                                             
3                                                                                                             
5                                                                                                             
7                                                                                                             
11                                                                                                            
-------
79                                                                                                            
83                                                                                                            
89                                                                                                            
97                                                                                                            
None   

Flowchart:

Flowchart: Sieve of Eratosthenes method, for computing prime numbers

Python Code Editor:

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

Previous: Write a Python program to generate all sublists of a list.
Next: Write a Python program to create a list by concatenating a given list which range goes from 1 to n.

What is the difficulty level of this exercise?

Test your Programming skills with w3resource's quiz.



Share this Tutorial / Exercise on : Facebook and Twitter

Python: Tips of the Day

Memory Management:

getrefcount will show how many times an object is used in the memory. It's a fantastic tool that can be used for memory management in any program and it's very convenient too.

Getrefcount will calculate the object usage at a low level ByteCode so it can tend to be higher than expected. For instance when you print a value that value is actually processed multiple times in the background inside the print function itself and getrefcount also counts the instance when the value is called with getrefcount method itself. So, it's safe to say that the count will actually always be at least 1 time higher than expected.

Here is a code to show how many times alphanumeric characters are referenced in a random code:

import sys
x_val = 20
x_val += 1

y_val = "Heritage"

x = sys.getrefcount(x_val)
y = sys.getrefcount(y_val)

print(x, y, sep="\n")

Output:

10
4