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
}

C++: // IncludingFiles
#include<iostream>
#include<vector>
#include<math.h>

// Defines
#define     MAX_NUMBER     (999999)
#define     MIN_NUMBER     (1)

// Using Namespace
using namespace std;

// Function
int main(){
	vector <int> PrimeNumbers;
	vector <int> input;
	vector <int> output;
	int i,buf,maxn,sz,root;
	bool flag = true;
	int a,b,m,n;

	// 入力
	while(cin >> buf){
		// 入力値のチェック
		if((buf < ((int)(MIN_NUMBER))) || (buf > ((int)(MAX_NUMBER)))){
			cerr << "InputError!!" << endl;
			return -1;
		}
		// 入力値をリストに追加
		input.push_back(buf);
	}

	// n の最大値を求めて maxn に代入
	sz = (int)input.size();
	maxn = input[0];
	for(i=1;i<sz;i++){
		if(maxn < input[i]){
			maxn = input[i];
		}
	}

	// 素数2 を 素数表PrimeNumbers に追加
	PrimeNumbers.push_back(2);

	// 3 から maxn までの整数が素数かどうかを調べ、素数であれば 素数表PrimeNumbers に追加
	for(i=3;i<=maxn;i+=2){
		// root に i の平方根を代入
		root = (int)sqrt(i);
		// sz に 素数表PrimeNumbers の大きさを代入
		sz = (int)PrimeNumbers.size();
		// i が 素数表PrimeNumbers に含まれている素数で割り切れないかを確認
		for(buf=0;buf<sz;buf++){
			if(PrimeNumbers[buf] > root){				// 平方根より大きいならば
				break;						// 内側のforループから抜ける
			}else if((i % PrimeNumbers[buf]) == 0){			// もし割り切れたら
				flag = false;					// flag を戻して
				break;						// 内側のforループから抜ける
			}
		}
		// flag が立っている (すなわち i は素数である) ならば i を 素数表PrimeNumbers に追加
		if(flag == true){
			PrimeNumbers.push_back(i);
		}
		// flag を元の状態に戻す (立てる)
		flag = true;
	}

	// n 以下の素数の個数を計測
	sz = (int)input.size();
	for(i=0;i<sz;i++){
		// a および flag の初期化
		a = 0;
		flag = false;

		// b の初期化
		b = (int)PrimeNumbers.size();

		// PrimeNumbers の最大値 <= input[i] となっていないかどうかを調べる
		if(PrimeNumbers[b-1] <= input[i]){
			n = b - 1;
			flag = true;
		}

		// 二分検索
		while (flag == false){
			m = (a + b) / 2;
			if(PrimeNumbers[m] > input[i]){
				b = m;
			}else if((PrimeNumbers[m] <= input[i]) && (PrimeNumbers[m+1] > input[i])){
				n = m;
				flag = true;
			}else if(PrimeNumbers[m] < input[i]){
				a = m;
			}else{
				cerr << "BinarySearchError!!" << endl << endl;
				cerr << "PrimeNumbers[" << m << "] = " << PrimeNumbers[m] << endl;
				cerr << "PrimeNumbers[" << (m + 1) << "] = " << PrimeNumbers[m+1] << endl;
				cerr << "input[" << i << "] = " << input[i] << endl;
				return -1;
			}
		}

		// 出力値をリストに追加
		output.push_back(n + 1);
	}

	// 出力
	sz = (int)output.size();
	for(i=0;i<sz;i++){
		cout << output[i] << endl;
	}

	return 0;
}

C++: #include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <cmath>
#include <string>
#include <sstream>
#include <iomanip>
#include <complex>
using namespace std;

#define ll long long
#define vvi vector< vector<int> >
#define All(X) X.begin(),X.end()
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define pb push_back 
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

#define MAXINT 1000000
bool isprime[MAXINT];
ll int sum[MAXINT];
void makeprime(){
	REP(i,MAXINT) isprime[i] = true;
	FOR(i,2,sqrt(MAXINT)+1){
		if(!isprime[i]) continue;
		FOR(j,i+1,MAXINT-1){
			if(j%i==0) isprime[j] = false;
		}
	}
}

int main(){
	makeprime();
	sum[0] = 0;
	sum[1] = 0;
	sum[2] = 1;
	/*FOR(i,3,MAXINT){
		if(isprime[i]) sum[i] = sum[i-1]+1;
		else sum[i] = sum[i-1];
	}*/
	ll int n;
	while(cin >> n){
		ll int ans = 0;
		REP(i,n) if(isprime[i]) ans++;
		cout << ans << endl;
	}
}

C++: #include<iostream>
using namespace std;
bool num[1000001];
int main(){
  for(int i=2; i<=1000; i++)
    if(!num[i])
      for(int j=i*i; j<1000001; j+=i)
	num[j] = true;
  int n;
  while(cin >>n){
    int ans = 0;
    for(int i=2; i<=n; i++)
      if(!num[i]) ans++;
    cout <<ans<<endl;
  }
  return 0;
}

C++: #include <stdio.h>
#include <iostream>

const int MAX_V = 10000;
int prime[MAX_V+1];

void init(){
    int i, k, v;
    for(i=2; i<=MAX_V; i++){
        prime[i] = 1;
    }
    for(i=2; i*i<=MAX_V; i++){
        if(prime[i]){
            for(k=2*i; k<=MAX_V; k+=i){
                prime[k]=0;
            }
        }
    }   
}

int isprime(int n){
    return prime[n];
}

int main(){
    init();
    int num;
    // while(1){
    while(std::cin >> num){
        int count=0;
        // scanf("%d", &num);
        for(int i=2; i<=num; i++){
            if(isprime(i)==1)
                count++;
        }
    printf("%d\n", count);
    }
    return 0;
}

C++: #include <stdio.h>
#include <vector>

using namespace std;

vector<int> ps;

int isprime(int n){
	vector<int>::iterator it;
	for(it=ps.begin();it!=ps.end();it++){
		if(n%(*it) == 0) return 0;
	}
	ps.push_back(n);
	return 1;
}

int main(){
	int n;
	while(scanf("%d", &n)!=EOF){

	int c=0;
	for(int i=2;i<=n;i++)
		if(isprime(i)) c++;

	printf("%d\n", c);
	}
}

C++: #include <iostream>
#include<stdio.h>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
#define MAX 1000000

bool is_prime[MAX];
ll prime[MAX];

ll found(ll a)
{
    ll p=0;
    for(ll i=0;i<=a;i++)
    {
        is_prime[i]=true;
    }
    is_prime[0]=false;
    is_prime[1]=false;
    for(ll i=2;i<=a;i++)
    {
        if(is_prime[i])
        {
            prime[p++]=i;
            for(ll k=2*i;k<=a;k=k+i)
            {
                is_prime[k]=false;
            }
        }
    }
    return p;
}

int main()
{
    ll n;
    while(cin>>n)
    {
        ll q;
        q=found(n);
        cout<<q<<endl;
    }
    return 0;
}

C++: #include <iostream>
#include <vector>

using namespace std ;

int main(){
	int n,cou=0 ;
	cin >> n ;

	/*üÍª1ÈºÈçÎfÍÈµ*/
	if(n <= 1){ return 0 ; }

	/*zñÉQðüêé*/
	vector<int> num ;
	num.push_back(2) ;

/*zñÉüÍµ½ÜÅÌïðüêé*/
	for(int i = 3 ; i <= n ; i+=2){
		num.push_back(i) ;
	}

	/*zñÌfÈOÌªÉ0ðüêé*/
	for(int i = 3 ; i <= n ; i+=2) {
		if(num[i/2] != 0){
			for(int j = 3 ; i * j <= n ; j+=2) {
				num[(i*j)/2] = 0 ;
				cou++;
			}
		}
	}

	/*0ÈOð\¦ifÌ\¦j*/
	
	cout << num.size()-cou << endl;
	
	return 0 ;
}

C++: #include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAX_N = 1e6+5;
int prime[MAX_N];
bool is_prime[MAX_N];
int sieve(){
    memset(is_prime, true, sizeof(is_prime));
    int p = 0;
    is_prime[0] = is_prime[1] = false;
    for(int i = 2;i < MAX_N;i++){
        if(is_prime[i]){
            prime[p++] = i;
            for(int j = 2*i;j < MAX_N;j+=i){
                is_prime[j] = false;
            }
        }
    }
    return p;
}

int main(){
    int n;

    while(~scanf("%d",&n)){
            int p = sieve();
//        printf("test :\n");
//        for(int i = 0;i < 10;i++){
//            printf("%d ",prime[i]);
//        }
//        cout <<endl;
        int num = upper_bound(prime, prime + p, n) - prime;
        printf("%d\n",num);
    }
}

C++: #include <iostream>
#include <fstream>

using namespace std;

void init(int *m) {
    m[1] = 0;
    m[2] = 1;
    for (int i = 3; i <= 1000000; i += 2)
        m[i] = 1;

    for (int i = 3; i <= 1000; i += 2) {
        if (m[i] == 0)
            continue;
        for (int j = 2; i * j <= 1000000; j++)
            m[i * j] = 0;
    }

    for (int i = 3; i <= 1000000; i++)
        m[i] += m[i-1];
}

int main() {

    #if 0
        ifstream cin("34870.in");
    #endif

    int *memo = new int[1000001];
    init(memo);

    int n;
    while (cin >> n) {
        cout << memo[n] << endl;
    }

    return 0;
}