Home » Python » Python programs

# Find all Prime numbers less than or equal to N using the Sieve of Eratosthenes algorithm in Python

In this tutorial, we will learn **how to find all Prime numbers less than or equal to N by using the Sieve of Eratosthenes algorithm in Python programming language?**

Submitted by Bipin Kumar, on October 09, 2019

As we all know that the **prime number** is an integer greater than 1 which is only divisible by 1 or itself. For example 2,3,5,7,11,.. etc. The value of **N** is given by the user. Before going to solve this problem, we will learn a little bit about the **Sieve of Eratosthenes** and it's an algorithm.

**What is the Sieve of Eratosthenes?**

It is a simple and ancient method for finding all Prime numbers less than or equal to **N**.

**Algorithm to find Prime numbers by Sieve of Eratosthenes**

- Initially, we will create a boolean array of size equal to the
**N**and mark each position in the array True. - We initialize a variable p as 2. If the variable is prime then mark each multiple of number False in the array and update the variable p by increment.
- Repeat
**step 2**until the square of the variable p is less than or equal to**N**. - Return, the elements in the array with True contains all Prime numbers.

**Implementation of the above algorithm using python program**

# input the value of N N=int(input("Input the value of N: ")) Primes=[True for k in range(N+1)] p=2 Primes[1]=False Primes[0]=False while(p*p<=N): if Primes[p]==True: for j in range(p*p,N+1,p): Primes[j]=False p+=1 for i in range(2,N): if Primes[i]: print(i,end=' ')

**Output**

Input the value of N: 50 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.