Sieve of Eratosthenes

• Problem Description

  
  Python Program to Read & Print Prime Numbers in a Range using Sieve of Eratosthenes.
  
  To find all the prime numbers less than or equal to a given integer n by Eratosthenes' method:
  
  Create a list of consecutive integers from 2 through n: (2, 3, 4, ..., n).
  
  Initially, let p equal 2, the smallest prime number.
  
  Enumerate the multiples of p by counting to n from 2p in increments of p, and mark them in the list (these will be 2p, 3p, 4p, ...; the p itself should not be marked).
  
  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 new number (which is the next prime), and repeat from step 3.
  
  When the algorithm terminates, the numbers remaining not marked in the list are all the primes below n.

• CODING ARENA

• n=int(input())

  sieve=set(range(2,n+1))

  while sieve:

      prime=min(sieve)

      print(prime,end="\n")

      sieve-=set(range(prime,n+1,prime))

   

  print()

• Test Case 1

  
  Input (stdin)

  10
  
  

  Expected Output

  2
  
  3
  
  5
  
  7

• Test Case 2

  
  Input (stdin)

  20
  
  

  Expected Output

  2
  
  3
  
  5
  
  7
  
  11
  
  13
  
  17
  
  19

✖

Share this Posts

• Share To Facebook Share To Twitter Share To Pinterest Share To Whatsapp Share To Linkedin Share To Tumblr Share To Telegram Share To Reddit Share To Gmail

Subscribe Our Newsletter