Go: package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func main() {
	num := make([]bool, 1000000)

	for sc.Scan() {
		var nmpr int

		n, _ := strconv.Atoi(sc.Text())

		lmt := int(math.Sqrt(float64(n)))

		for i := 2; i <= lmt; i++ {
			for j := 2; i*j <= n; j++ {
				if !num[i*j] {
					num[i*j] = true
				}
			}
		}

		for t := 2; t <= n; t++ {
			if !num[t] {
				nmpr++
			}
		}

		fmt.Println(nmpr)
	}

}

Python: import sys

L = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]

def is_prime_2(n):
  a = int(n ** 0.5)
  for i in L:
    if i > a:return True
    if n % i == 0:return False
  return True

def prime_count(n):
  result = 0
  if n >= 2:result+=1
  for i in range(3,n+1,2):
    if is_prime_2(i):result+=1
  return result

for n in sys.stdin:
  print(prime_count(int(n)))

Python: import sys
m=10**6;a=[1]*m;a[0:2]=0,0
for i in range(2,999):
 if a[i]>0:
  for j in range(i*2,m,i):a[j]=0
for i in range(m):a[i]+=a[i-1]
for e in sys.stdin:print(a[int(e)])

Python: import sys


max_v = max(int(string) for string in sys.stdin)

prime_list = [2]
for i in range(2, max_v + 1):
    for prime in prime_list:
        if i % prime == 0: break
    else:
        prime_list.append(i)

cnt = 0
for string in sys.stdin:
    for i in range(int(string) + 1):
        cnt += 1 if i in prime_list else 0
    print(cnt)

Python: import math
def lb(a,x):
    l=0
    r=len(a)-1
    while l<r:
        mid=int((l+r)/2)
        #print "l=",l,' r=',r
        if a[mid]<x:
            l=mid+1
        else:
            r=mid
    return l

#maxn=1000001 // Wrong Answer?
maxn=1000010
a=[False for i in xrange(maxn)]
for i in xrange(2,int(math.sqrt(maxn))):
    for j in xrange(i+i,maxn,i):
        a[j]=True
b=[]
for i in xrange(2,maxn):
    if not a[i]:
        b.append(i)
while True:
    try:
        n=input()
        f=lb(b,n)
        if b[f]==n:
            print(f+1)
        else:
            print(f)
    except EOFError: break

Python: while True:
 a=int(input())
 X=[i for i in range(2,a+1)]
 Y=[]
 while True:
   k=X[0]
   X=[i for i in X if i % k !=0]
   Y.append(k)
   if len(X)==0:
     break
 print(len(Y))

Python: prime_num = 0
for i in range(int(raw_input())):
    y = i+1
    x = y / 2
    while x > 1:
        if y % x == 0:
            break
        x -= 1
    else:
        prime_num += 1
print(prime_num-1)

Python: # coding=utf-8

###
### for atcorder program
###

import sys
import math
import array

# math class
class mymath:
    ### pi
    pi = 3.14159265358979323846264338

    ### Prime Number
    def pnum_eratosthenes(self, n):
        ptable = [0 for i in range(n+1)]
        plist = []

        for i in range(2, n+1):
            if ptable[i]==0:
                plist.append(i)
                for j in range(i+i, n+1, i):
                    ptable[j] = 1
        return plist

    def pnum_fermat(self,n):
        pnum = 0
        for i in range(2,n+1):
            if i % 2 == 0 and i != 2:
                continue
            if pow(2,i-1,i) == 1:
                pnum += 1
        return pnum

    ### GCD
    def gcd(self, a, b):
        if b == 0:
            return a
        return self.gcd(b, a%b)

    ### LCM
    def lcm(self, a, b):
        return (a*b)//self.gcd(a,b)

mymath = mymath()

### output class
class output:
    ### list
    def list(self, l):
        l = list(l)
        print(" ", end="")
        for i, num in enumerate(l):
            print(num, end="")
            if i != len(l)-1:
                print(" ", end="")
        print()

output = output()

### input sample
#i = input()
#A, B, C = [x for x in input().split()]
#N, K = [int(x) for x in input().split()]
#inlist = [int(w) for w in input().split()]
#R = float(input())
#A = [int(x) for x in input().split()]
#for line in sys.stdin.readlines():
#    x, y = [int(temp) for temp in line.split()]

### output sample
#print("{0} {1} {2:.5f}".format(A//B, A%B, A/B))
#print("{0:.6f} {1:.6f}".format(R*R*math.pi,R*2*math.pi))
#print(" {}".format(i), end="")

def main():
    for line in sys.stdin.readlines():
        n = int(line)
        n_pn = mymath.pnum_eratosthenes(n)
        print(len(n_pn))

if __name__ == '__main__':
    main()

Python: import sys,random

rand = random.randint

def prime(n):
	if n == 2:
		return True
	if n < 2 or n & 1 == 0:
		return False
	d = (n-1) >> 1
	while d & 1 == 0:
		d >>= 1
	
	for i in range(4):
		a = rand(1,n-1)
		t = d
		y = pow(a,t,n)
		while t != n-1 and y != 1 and y != n-1:
			y = pow(y,2,n)
			t <<= 1
		if y != n-1 and t & 1 == 0:
			return False
	return True

a = [prime(i) for i in range(1000000)]

for s in sys.stdin:
	i = int(s)
	print(a[:i+1].count(True))

Python: prime = [1 for i in range(1000000)]

prime[0] = 0
prime[1] = 0

for i in range(1000):
    if prime[i] == 1:
        for j in range(2, 1000000):
            try:
                prime[i * j] = 0
            except:
                break

for i in range(1, 1000000):
    prime[i] = prime[i] + prime[i - 1]

while True:
    try:
        n = int(input())
        print(prime[n])
    except:
        break

Python: 
import math

m=999999
s=int(math.sqrt(m)+1)
li=[0]*m
li[0]=1
for i in range(1,s):
    if li[i]==0:
        li[i*2+1::i+1]=[1 for e in range(len(li[i*2+1::i+1]))]
while True:
    try:n=int(input())
    except:break
    print(len([i for i in li[:n:] if i==0]))

Python: import sys
m=10**6;a=[0,0]+[1]*m
for i in range(2,999):
 if a[i]>0:
  for j in range(i*2,m,i):a[j]=0
for e in sys.stdin:print(sum(a[:int(e)+1]))

Python: import sys
a=[0,0,1]+[1,0]*499999
for i in range(3,999,2):
 if a[i]:a[i*i::i]=[0]*len(a[i*i::i])
for e in sys.stdin:print(sum(a[:int(e)+1]))

Python: import sys
a=[0,0,1]+[1,0]*499999
for i in range(3,999,2):
 if a[i]:a[i*2::i]=[0]*len(a[i*2::i])
for e in sys.stdin:print(sum(a[:int(e)+1]))

Python: import sys,random

rand = random.randint

def prime(n):
	if n == 2: return True
	if n < 2 or n & 1 == 0: return False
	return pow(2, n-1, n) == 1

a = [prime(i) for i in range(1000000)]

for s in sys.stdin:
	i = int(s)
	print(a[:i+1].count(True))

Python: # -*- coding:utf-8 -*-
import sys

# n??\???????´???°?????°?????????
def prime(n):
    l = range(0,n+1)
    i,k = 0,2
    result = 1

    if n >= 3:
        prime_nums = [2, 3]
    else:
        prime_nums = []

    while i <= n:
        while l[i] > k:
            result = l[i]%k
            k = k+1
            if result == 0:
                break
            if (l[i]-1 == k) and (result != 0):
                prime_nums.append(l[i])

        i, k = i+1, 2

    #return prime_nums
    return len(prime_nums)

while True:
    try:        
        psum = prime(int(input()))
        print(psum)
    except:
        break

Python: import sys
  
N = 1000000
primes = [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] = [0] * len(primes[(i*i)//2::i])
  
for i in sys.stdin:
    n = int(i)
    if n < 3:
        print(n-1)
    else:
        print(sum(primes[:(n+1)//2])+1)