埃氏筛

链接描述
链接描述

#include<bits/stdc++.h>
using namespace std;
int a[100010]={};
int Eratosthenes(int n){
    memset(a,1,sizeof(a));
	int sum=1;
    for(int i=2;i<n;i++){
        if(a[i]==0){continue;}
    	for(int j=2;i*j<n;j++){
        	a[i*j]=0;
        }
        sum++;
    }
    return sum;
}
int main(){
    int n;
    cin>>n;
    cout<<Eratosthenes(n);
	return 0; 
}