Sieve of Eratosthenes Python

Prime Number

The term prime number refers to those integers that have exactly two factors One and the number itself. Some of the prime numbers are 2, 3, 5, 7, 11, 13, 17, and so on. Except for 2, which is the lowest prime number and the only even prime number, all prime numbers are odd numbers.

Sieve of Eratosthenes

The Sieve of Eratosthenes is a technique for evaluating prime and composite numbers among a series of numbers. There are several ways for determining prime and composite numbers, including factorization and division. However, in the case of the Sieve of Eratosthenes method, it is simple to quickly list the prime numbers among a group of numbers. It works on the prime factor cancellation principle Using the Sieve of Eratosthenes method we can efficiently and easily calculate the prime numbers in between the range of 1 to 10 million or so.

Let us take an example to understand this technique better
Example:
Step 1: First, make a list and initialize it with the number from 1 to 100. And strikethrough the one from in the list as it is not a prime number.

Step 2: Now strikethrough all the numbers which are multiples of two but leave two as it is.

Step 3: Now strikethrough all the numbers that are multiples of 3, 5, and 7 and leave the rest of the number as it is.

Step 4: Now if we look we would not find the multiples of 11, 13, 17, and 19.

Step 5: Now the numbers which are not strikethrough in the list are actually prime numbers.
2, 3, 5,7, 11, 13,17,19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, and 97.

Simple Python program for Prime Number

if __name__ == "__main__":
    def checkPrime(n):
        # Check if n is less than 1
        #Then return false
        if n <= 1 :
            return False

        # Loop from 2 to n-1
        for p in range(2, n):
            #Check if n is divisible by p
            if n % p == 0:
                return False
        return True

    # Function to print prime numbers
    def printPrimeNumber(n):
        #Loop from 2 to n+1 to check
        for p in range(2, n + 1):
            #Check if p is a prime number
            if checkPrime(p):
                #If p is a prime nuber then print it
                print(p, end = " ")

    print("Prime Numbers from 1 to 100 are= ",printPrimeNumber(100))

pass

Input: 100
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.

Run this code on Interviewbit.

Explanation:

• Start a loop from 2 to n.
• Check if the n is divided by the current iterating number.
• If n is divisible then return false otherwise return true.
• Print the number.

Time Complexity: As there are two loops running one to track the count of numbers another is running inside a function which is called in each iteration of the counter loop so time complexity will be O(n*n).
Space Complexity: Here no extra space is used other than some variables which are independent of the input number so space complexity will be O(1).

Sieve of Eratosthenes Python program for prime numbers

if __name__ == "__main__":
    #Function to print prime numbers useing Sieve Of Eratosthenes method
    def SieveOfEratosthenes(n):
        primeNumbers = []
        #Initialize the list as true
        for i in range(n+1):
            primeNumbers.append(True)

        #variable to track the loop and
        #which number will be marked as false    
        m = 2
        #Loop will run till n
        while (m * m <= n):
            if (primeNumbers[m] == True):
                # Update all multiples of m and put false
                for i in range(m * m, n+1, m):
                    primeNumbers[i] = False
            #update m
            m += 1

        # Print all prime numbers
        for m in range(2, n+1):
            #Check if m is prime or not
            if primeNumbers[m]:
                print(m),
     #Call the driver function
    SieveOfEratosthenes(100)
pass

Input: 100
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.

Run this code on Interviewbit.

Explanation:

• Take an empty list of size n.
• Initialize the list as True using a loop.
• Now take a variable and initialize it as 2 because 1 is not a prime number.
• Now start a loop which will run till n.
• And put all the indexes in the list as false which are multiple of m.
• Now repeat this step until m*m<=n and then come out of the loop.
• Now start another loop starting from 2 to n and check if the index is true in the list if it is true then print the number otherwise continue.

Time complexity: O(n*(log(log(n)))
Space Complexity: O(n), we are using a List of size n to keep track of the numbers visited.