Advertisement
Guest User

Praxis--Sieve of Eratosthenes

a guest
Mar 31st, 2010
725
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.44 KB | None | 0 0
  1. #!/usr/bin/env python
  2.  
  3. #primelist.py
  4.  
  5. #Write a function that takes a single argument n and returns a list of prime numbers
  6. #less rthan or equal to n using the optimized sieving algorithm described above.
  7. #Apply the function to the argument 15485863 and count the number of primes returned.
  8.  
  9. import math
  10.  
  11. Majprimlst = []
  12.  
  13. def buildmajprimes():
  14.     LIMIT = 100001
  15.     nbrlst = range(LIMIT)
  16.     lstofprimes = []
  17.     indx = 0
  18.     while indx < (LIMIT - 2):
  19.         indx += 2
  20.         sqsw = True
  21.         if nbrlst[indx] != 0:
  22.             lstofprimes.append(indx)
  23.             if sqsw:
  24.                 nwindx = indx**2
  25.                 sqsw = False
  26.             while nwindx < LIMIT:
  27.                 nbrlst[nwindx] = 0
  28.                 nwindx += indx
  29.         if indx == 2: indx = 1
  30.     return lstofprimes    
  31.  
  32. def buildlist(num):
  33.     global Majprimlst
  34.     lstret = []
  35.     Majprimlst = buildmajprimes()
  36.     for x in Majprimlst:
  37.         if (x**2) <= num:
  38.             lstret.append(x)
  39.         else:
  40.             break
  41.     return lstret
  42.  
  43.    
  44.  
  45.  
  46. def main():
  47.     while 1 == 1:
  48.         nbr_in = raw_input('Enter an integer to find the number of prime numbers less than or = to n or 0 to exit: ')
  49.         nbr_in = int(nbr_in)
  50.         if nbr_in == 0: break
  51.         else:
  52.             thelist = buildlist(nbr_in)
  53.             print 'The number of primes <= ',nbr_in, ' is ',len(thelist)
  54.     return 0
  55.  
  56.  
  57.  
  58.  
  59. if __name__ == '__main__':
  60.     main()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement