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