Sieve of Eratosthenes in Python

Processing.py
1

Hello All, I working on a python project and I am confused sieve of eratosthenes coding problem. The problem statement is Given a number n, print all primes smaller than or equal to n. It is also given that n is a small number.

A prime number is a number that is divisible by only two numbers – themselves and 1

Example:
Input: n =10
Output: 2 3 5 7

I have taken this code reference from here. Can anyone explain me with the help of this code, how sieve of eratosthenes program works? or explain with another example?

def isPrime(n):
     
    # Corner case
    if n <= 1 :
        return False
 
    # check from 2 to n-1
    for i in range(2, n):
        if n % i == 0:
            return False
 
    return True
 
# Function to print primes
def printPrime(n):
    for i in range(2, n + 1):
        if isPrime(i):
            print(i, end = " ")
2

This is a Processing forum, so here’s something that uses Processing.py / Python Mode, that rearranges the example in a way you may find easier to comprehend –

# set framerate to 1 frame every 2 seconds
def setup(): frameRate(0.5)

def draw():
    # loop through all of the numbers between 2 and framecount
    for i in range(2, frameCount):
        # divide the framecount by every number from 2 up to framecount
        if frameCount % i == 0:
            # if the remainder of any division is zero, 
            # the framecount divides evenly by i, 
            # therefore it is not a prime number
            print(
'{} is not prime because it divides evenly into {}'.format(frameCount, i)
            )
            # exit the loop immediately and start again on the next frame
            return
    # if the loop didn't exit, the framecount is a prime number
    print('{} is prime'.format(frameCount))
2 Likes
3

You may find this discussion interesting, which is on Python Software Foundation Discourse:

1 Like