how to use sieve algorithm in python?

Answers

•   
  

  import math
  
  print ("Enter the a number")
  number = int(input())
  
  primes = []
  for i in range(2,number+1):
      primes.append(i)
  
  i = 2
  #from 2 to sqrt(number)
  while(i <= int(math.sqrt(number))):
      #if i is in list
      #then we gotta delete its multiples
      if i in primes:
          #j will give multiples of i,
          #starting from 2*i
          for j in range(i*2, number+1, i):
              if j in primes:
                  #deleting the multiple if found in list
                  primes.remove(j)
      i = i+1
  
  print (primes)
  

   

  
  
• Why sqrt?? And plz explain the loop of j and it's 3 parameters
  - Prathamesh Saraf
• If there is no factor of a number between 2 and square root of that number then there can't be any factor between square root of that number and the number itself. If a*b = n, then either a or b must be less than sqrt(n) or both may be equal to sqrt(n). For exmple, 16 has 2, 4 and 8 as its factors. So, 2*8 = 16, 4*4 =16. 4*4 is the case of sqrt(n)*sqrt(n). If we can have any other factor after 4, it has already dealt before e.g., 8*2 = 16 is dealt in the case of 2*8.
  - Amit Kumar
• range(i*2, number+1, i) - i*2 - We begin from 2*i. number+1 - We will go till number+1. i - We will take a step of i in every iteration. For example, if i is 3 then 3*2 is 6, take a step of i in next iteration, so 6+3, i is 9 in next iteration and so on.
  - Amit Kumar
• why did you do this while(i <= int(math.sqrt(number))):----number is already in the int form why typecast it again?
  - Prathamesh Saraf
• Yes, the number is in the int but its square root may not be an int.
  - Amit Kumar

---