java

import java.util.*;

class Main{
    static int N = 1000010;
    static boolean[] st = new boolean[N];
    static int[] primes = new int[N];
    static int cnt = 0;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        getPrimes2(n);
        System.out.println(cnt);
    }
    //朴素筛法 nlogn
    static void getPrimes(int n){
        for(int i = 2;i <= n;i++){
            if(st[i] == false){//没有被筛过说明是质数
                //primes[cnt++] = n;
                cnt++;
            }
            for(int j = i+i;j<=n;j+=i){
                st[j] = true;
            }
        }
    }
    //朴素筛法改进 nloglogn
    static void getPrimes1(int n){
        for(int i = 2;i <= n;i++){
            if(st[i] == false){//没有被筛过说明是质数
                //primes[cnt++] = n;
                cnt++;
                for(int j = i+i;j<=n;j+=i){
                    st[j] = true;
                }
            }
        }
    }
    //线性筛法
    static void getPrimes2(int n){
        for(int i = 2;i <= n;i++){
            if(st[i] == false) primes[cnt++] =i; //如果没有筛过说明是质数,加到里面去
            for(int j = 0; primes[j] <=n/i;j++){
                st[primes[j]*i] =true;
                if(i%primes[j] == 0) break;
            }
        }
    }
}