Guest User

Praxis--Sieve of Eratosthenes

a guest
Mar 31st, 2010
514
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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()
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×