Advertisement
zhu2qian1

Sieve of Eratosthenes

Feb 1st, 2020
389
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.96 KB | None | 0 0
  1.  
  2. # the sieve of Eratosthenes
  3. # import math for sqrt()
  4. from math import sqrt
  5. def theSieve(maxNum):
  6.     # create a list w/o 1
  7.     searchList = list(range(2, maxNum + 1))
  8.     # create a list to store prime numbers
  9.     primeList = []
  10.     # begin the sieve process
  11.     while True:
  12.         # if the first number of searchList is bigger than sqrt(maxNum),
  13.         # transfer all the rest numbers from searchList into primeList
  14.         if searchList[0] >= sqrt(maxNum):
  15.             for n in range(len(searchList)):
  16.                 primeList.append(searchList.pop(0))
  17.         # check if searchList is empty
  18.         if len(searchList) == 0:
  19.             return primeList
  20.         # transfer the first number from searchList into primeList
  21.         primeList.append(searchList.pop(0))
  22.         # delete the multiples of the transfered number
  23.         for n in searchList:
  24.             if n % primeList[-1] == 0:
  25.                 searchList.remove(n)
  26.  
  27. print(theSieve(61))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement