Submission #3428238

---

Source Code Expand

#include<bits/stdc++.h>

using namespace std;
const int N=1e5+5;
bool f[N];
int s[N];
int n;
inline int read()
{
	int ck=0;
	char fu=1;
	char c;
	for(;!isdigit(c);c=getchar())
		if(c=='-')
			fu=-1;
	for(;isdigit(c);c=getchar())
		ck=ck*10+c-'0';
	return fu*ck;
}
void prime(){
	int k=0;
	memset(f,1,sizeof(f));
	f[1]=0;
	for(int i=2;i<=n;i++){
		if(f[i]) s[k++]=i;
		for(int j=0;j<k&&i*s[j]<=n;j++) f[i*s[j]]=0;
	}
}
int main()
{
	int ans=0;
	n=read();
	prime();
	for(int i=1;i<n;i++)
		if(f[i]) 
			ans++;
	cout<<ans<<endl;
	return 0;
}

Submission Info

Judge Result