Write a program which reads an integer n and prints the number of prime numbers which are less than or equal to n. A prime number is a natural number which has exactly two distinct natural number divisors: 1 and itself. For example, the first four prime numbers are: 2, 3, 5 and 7.
import sys
import math

N = 1000000
primes = [1] * N
primes[0] = 0
primes[1] = 0
primes[4::2] = [0] * len(primes[4::2])

for i in range(3,int(math.sqrt(N)),2):
    if primes[i]:
        primes[i*i::i*2] = [0] * len(primes[i*i::i*2])

for i in sys.stdin:
        n = int(i)
        print(sum(primes[0:n]))
import sys
from array import array

N = 1000000
primes = array('I',[1]) * (N//2)
primes[0] = 0

for i in range(3,int(N**0.5),2):
    if primes[i//2]:
        primes[(i*i)//2::i] = array('I',[0]) * len(primes[(i*i)//2::i])

for i in sys.stdin:
    n = int(i)
    if n < 4:
        print(n-1)
    else:
        print(sum(primes[:(n+1)//2])+1)