DEV Community

Cover image for Sieve of Eratosthenes
Deepak Raj
Deepak Raj

Posted on • Edited on

9 5

Sieve of Eratosthenes

Sieve of Eratosthenes

Topic: Sieve of Eratosthenes

In mathematics, the sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to any given limit. It does so by iteratively marking as composite the multiples of each prime, starting with the first prime number, 2.

Example:-

Input : n = 10
Output : 2 3 5 7 

Input : n = 20 
Output: 2 3 5 7 11 13 17 19
Enter fullscreen mode Exit fullscreen mode

Steps to Implement sieve of Eratosthenes

  • Create a list of consecutive integers from 2 to n: (2, 3, 4, …, n).

  • Initially, let p equal 2, the first prime number.

  • Starting from p2, count up in increments of p and mark each of these numbers greater than or equal to p2 itself in the list. These numbers will be p(p+1), p(p+2), p(p+3), etc..

  • Find the first number greater than p in the list that is not marked. If there was no such number, stop. Otherwise, let p now equal this number (which is the next prime), and repeat from step 3.

Implementation of Sieve of Eratosthenes in Python3.

def get_primes(n):
  m = n+1
  #numbers = [True for i in range(m)]
  numbers = [True] * m #EDIT: faster
  for i in range(2, int(n**0.5 + 1)):
    if numbers[i]:
      for j in range(i*i, m, i):
        numbers[j] = False
  primes = []
  for i in range(2, m):
    if numbers[i]:
      primes.append(i)
  return primes

print(get_primes(25))
Enter fullscreen mode Exit fullscreen mode

Hostinger image

Get n8n VPS hosting 3x cheaper than a cloud solution

Get fast, easy, secure n8n VPS hosting from $4.99/mo at Hostinger. Automate any workflow using a pre-installed n8n application and no-code customization.

Start now

Top comments (1)

Collapse
 
muhimen123 profile image
Muhimen

Cool, you are going advanced! Keep it up.

A Workflow Copilot. Tailored to You.

Pieces.app image

Our desktop app, with its intelligent copilot, streamlines coding by generating snippets, extracting code from screenshots, and accelerating problem-solving.

Read the docs

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay