C++ :

#include <bits/stdc++.h>
using namespace std;
const int N = 1000010;
int primes[N],cnt;
bool f[N];//标记是否是素数

//朴素的素数筛 时间复杂度：O(n*log2n) 
void get_primes(int n){
	for(int i = 2;i <= n;i++){
		//如果是素数 
		if(!f[i]){
			primes[cnt++] = i;
		}
		
		for(int j = i + i;j <= n;j = j + i){
			f[j] = true;
		}
	}
} 

//优化版本：只需要将2~p-1之间的质数的倍数标记为非素数
//时间复杂度O(nloglogn) 
//埃筛 
void get_primes2(int n){
	for(int i = 2;i <= n;i++){
		//如果是素数 
		if(!f[i]){
			primes[cnt++] = i;
			for(int j = i + i;j <= n;j = j + i){
				f[j] = true;
			}
		}
	}
}  

//埃筛再优化 
void get_primes3(int n){
	cnt = n - 1;
	for(int i = 2;i * i <= n;i++){
		//如果是素数 
		if(!f[i]){
			for(int j = i + i;j <= n;j = j + i){
				if(!f[j]){
					f[j] = true;
					cnt--; 
				}
			}
		}
	}
} 

//线性筛
//原理：n只会被最小质因子筛选掉，所有的合数一定被筛掉 
void get_primes4(int n){
	for(int i = 2;i <= n;i++){
		if(!f[i]) primes[cnt++] = i;
		for(int j = 0;primes[j] <= n / i;j++){
			f[primes[j] * i] = true;
			//primes[j]是i的最小质因子，也就一定是primes[j]*i的最小质因子 
			if(i % primes[j] == 0) break;
		} 
	}
} 
 
int main() {
	int n;
	cin>>n;
	get_primes4(n);
	cout<<cnt;
	return 0;
}