#!/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()