埃氏筛法

#include <iostream>
using namespace std;
int n ,  num;
bool un_prime[1000005] ;//存储数是不是质数(true为不是)
int main(){
	cin >> n ;
	for(int i = 2 ; i <= n ; i ++)
		if(!un_prime[i]){//开始筛选，若是质数(为false)
        
			num ++ ;//数量加一
			for(int j = i * 2 ; j <= n ; j += i)
				un_prime[j] = true ;//同时它的倍数全是合数
		}
	cout << num ;//输出~
	return 0 ;
}

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
bool f[N];
int primes[N],n,k; 
int main(){
	scanf("%d",&n);
	f[0]=f[1]=true;
	for (int i=2;i<=n;i++){
		if (!f[i])primes[++k]=i;
		for (int j=1;primes[j]*i<=n;j++){
			f[primes[j]*i]=true;
			if (i%primes[j]==0)break;
		} 
	}
	printf("%d",k);
	return 0;
}