Go: package main
import (
	"fmt"
	"os"
	"strconv"
	"bufio"
	//"math"
)

var sc = bufio.NewScanner(os.Stdin)

func main(){
	for sc.Scan(){
		n := nextInt()
		fmt.Println(calc(n))
	}
}

func calc(n int)int{
	// エラトステネスで数え上げる
	// 最初から999999まで用意しておいて入力のたびO(1)で出すのとどっちが速いのかはわからん
	eratos := make([]bool, n+1)
	c := 0
	for i:=2; i<len(eratos); i++{
		if eratos[i] == false{
			c++
			for j:=i*i; j<len(eratos); j+=i{
				eratos[j]=true
			}
		}
	}
	return c
}

func next()string{
	return sc.Text()
}

func nextInt()int{
	a, _ := strconv.Atoi(next())
	return a
}

Python: import math

while True:
    try:
        r = int(input())

        A = [i for i in range(2, r+1)]
        P = []
        time = 0

        while True:
            prime = min(A)

            if prime > math.sqrt(r):
                break

            P.append(prime)

            i = 0
            while i < len(A):
                if A[i] % prime == 0:
                    A.pop(i)
                    continue
                i += 1
        for a in A:
            P.append(a)

        print(len(P))

    except EOFError:
        break

Python: while True:
    try:
        n = int(input())
        primes = [1 for _ in range(n+1)]
        for i in range(4, n+1, 2):
            primes[i] = 0
        for i in range(6, n+1, 3):
            primes[i] = 0
        for i in range(10, n+1, 5):
            primes[i] = 0
        for i in range(14, n+1, 7):
            primes[i] = 0
        primes[0], primes[1] = 0, 0
        print(sum(primes))
    except:
        break

Python: while True:
    try:
        a = int(input())
        primes = [1] * (a+1)
        for i in range(2, int(a**0.5)+1):
            if primes[i]==1:
                for j in range(i*i, a+1, i):
                    primes[j] = 0
        print(sum(primes)-2)
    except EOFError:
        break

Python: limit=999999
prime=[0,1]+[0 if i%2==0 else 1 for i in range(3,limit+1)]
for i in range(3,int(limit**0.5)+1):
    if prime[i-1]==1:
        for j in range(i**2,limit+1,i):
            prime[j-1]=0
            
while True:
    try:
        n=int(input())
    except EOFError:
        break
    print(sum(prime[:n]))

Python: def sieve_of_erastosthenes(num):    
    input_list = [False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else True for i in range(num)]
    input_list[0] = input_list[1] = False
    input_list[2] = input_list[3] = input_list[5] = True

    for serial in range(3, int(num ** 0.5) + 1, 2):
        
        if input_list[serial] is True:
            
            for s in range(serial ** 2, num, serial): 
                input_list[s] = False

    return sum(input_list)

print(sieve_of_erastosthenes(1000000))

Python: import sys
m=166666;s=[1]*m;t=[1]*m
for i in range(m):
 for j in range(2):
  if (s[i],t[i])[j]:
   k=6*i+[5,7][j];n=[i+k,k-i-2]
   s[n[j]::k]=[0]*len(s[n[j]::k])
   t[n[1-j]::k]=[0]*len(t[n[1-j]::k])
for e in map(int,sys.stdin):
 print([e-1,sum(s[:(e+1)//6])+sum(t[:(e-1)//6])+2][e>3])

Python: prime=[True]*1000000
np=[0]*1000000
for i in range(2,1000):
    if prime[i]:
        for j in range(i*2,1000000,i):
            prime[j]=False

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

Python: def prime_calc(n):
    if n < 2:
        return 0
    else:
        i = 2
        while i*i <= n:
            if n % i == 0:
                return 0
            else:
                i = i + 1

    return 1

def prime(n):
    cnt = 0
    for i in range(1, n+1):
        ans = prime_calc(i)
        if ans == 1:
           cnt = cnt + 1

    return cnt


def main():
    l = []

    for line in sys.stdin:
        l.append(int(line))

    for line in l:
        print(prime(line))

if __name__ == "__main__":
    main()

Python: import sys
  
lalala = 1000000//30 + 1
f = ([1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0]+[1,0]*7 ) * lalala
f = [0,0,1,1] + f[3:-20]

i = 2
while i < 1000:
    if f[i] == 1:
        j = i * i
        while j <= 1000000:
            f[j] = 0
            j += i + i
    i += 2

for n in sys.stdin:
    i = int(n)
    print(sum(f[:i + 1]))

Python: # AOJ 0009 Prime Number
# Python3 2018.6.9 bal4u

MAX = 1000000
SQRT = 1000     # sqrt(MAX)

prime = [True for i in range(MAX)]
def sieve():
	for i in range(2, MAX, 2):
		prime[i] = False
	for i in range(3, SQRT, 2):
		if prime[i] is True:
			for j in range(i*i, MAX, i):
				prime[j] = False

sieve()
cnt = [0 for i in range(MAX+1)]
cnt[2] = 1
f = 1
for i in range(3, MAX, 2):
	if prime[i] is True:
		f += 1;
	cnt[i] = f
	cnt[i+1] = f
	
while True:
    try:
        print(cnt[int(input())])
    except EOFError:
        break

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 e in sys.stdin:print(sum(a[:int(e)+1]))

Python: import sys
x = 500000
f = [0, 1] * xx
i = 3

while i * i <= 2 * xx:
    if f[i] == 1:
        j = i * i
        while j <= 2 * xx:
            f[j] = 0
            j += i + i
    i += 2

f.pop(0)
f.pop(1)

for n in sys.stdin:
    i = int(n)
    if i < 2:
        print(0)
    else:
        print(sum(f[:i - 1]))

Python: import math
import sys

is_prime = [i for i in range(1000000)]

is_prime[0] = is_prime[1] = False

for i in range(2,1000000):
    is_prime[i] = True

for i in range(2,1000000):
    if i*i >= 1000000:
        break
    if is_prime[i]:
        for j in range(i*i,1000000,i):
            is_prime[j] = False

n_prime = [i for i in range(1000000)]
cnt = 0
for i in range(1000000):
    if is_prime[i]:
        cnt += 1
    n_prime[i] = cnt

a=[]
for i in sys.stdin:
    a.append(int(i))
for i in range(0,len(a)):
    print(n_prime[a[i]])

Python: MAX = 999999

def is_prime(n):
  if n == 2:return True
  if n % 2 == 0:return False
  for i in range(3,int(n**0.5)+1,2):
    if n % i == 0:return False
  return True

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

while 1:
  print(prime_list(int(input())))

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
prime=[False]*1000000
for i in range(2,1001):
    for j in range(i*2,1000000,i):
        prime[j]=True

for n in sys.stdin:
    cnt=0
    for i in range(2,int(n)+1):
        if not prime[i]:
            cnt+=1
    print(cnt)

Python: from math import sqrt
cash = {}
def isprime(n):
    if n in cash:
        return cash[n]
    for i in range(3, int(sqrt(n)+1))[0::2]:
        if n % i == 0:
            cash[n] = 0
            return 0
    cash[n] = 1
    return 1

from sys import stdin
for i in stdin:
    print(sum(isprime(n) for n in range(2, int(i)+1)[1::2]) + 1)

Python: def mk_table(n):
    res = [1] * (n + 1)
    res[:2] = 0, 0

    for i in range(2, n):
        if i ** 2 > n:
            break

        if res[i] == 1:
            for j in range(2, n // i + 1, i):
                res[i * j] = 0

    return res


tbl = mk_table(999999)
try:
    while 1:
        print(len([x for x in tbl[:int(input())+1] if x == 1]))
except Exception:
    pass

Python: import math


def sieve_of_erastosthenes(num):
    input_list = [False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else True for i in range(num)]
    input_list[0] = input_list[1] = False
    input_list[2] = input_list[3] = input_list[5] = True
    sqrt = math.sqrt(num)

    for serial in range(3, num, 2):
        
        if serial >= sqrt:
            return input_list

        for s in range(serial ** 2, num, serial): 
            input_list[s] = False


if __name__ == '__main__':
    while True:
        try:
            n = int(input())
        except:
            break

        if 5 >= n:
            print(1)

        else:
            input_list = sieve_of_erastosthenes(n)

            print(sum(input_list))