Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #!/usr/bin/env python
- #primelist.py
- #Write a function that takes a single argument n and returns a list of prime numbers
- #less rthan or equal to n using the optimized sieving algorithm described above.
- #Apply the function to the argument 15485863 and count the number of primes returned.
- import math
- Majprimlst = []
- def buildmajprimes():
- LIMIT = 100001
- nbrlst = range(LIMIT)
- lstofprimes = []
- indx = 0
- while indx < (LIMIT - 2):
- indx += 2
- sqsw = True
- if nbrlst[indx] != 0:
- lstofprimes.append(indx)
- if sqsw:
- nwindx = indx**2
- sqsw = False
- while nwindx < LIMIT:
- nbrlst[nwindx] = 0
- nwindx += indx
- if indx == 2: indx = 1
- return lstofprimes
- def buildlist(num):
- global Majprimlst
- lstret = []
- Majprimlst = buildmajprimes()
- for x in Majprimlst:
- if (x**2) <= num:
- lstret.append(x)
- else:
- break
- return lstret
- def main():
- while 1 == 1:
- nbr_in = raw_input('Enter an integer to find the number of prime numbers less than or = to n or 0 to exit: ')
- nbr_in = int(nbr_in)
- if nbr_in == 0: break
- else:
- thelist = buildlist(nbr_in)
- print 'The number of primes <= ',nbr_in, ' is ',len(thelist)
- return 0
- if __name__ == '__main__':
- main()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement