 # 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