Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- #define mx 100005
- int seive(int m)
- {
- vector<int>prime;
- bool vis[m]={0};
- int x=sqrt((int)m);
- for(int i=3; i<=x; i+=2)
- {
- if(vis[i]==0)
- {
- for(int j=i*i; j<m; j+=2*i)
- vis[j]=1;
- }
- }
- int cnt=1;
- for(int i=3; i<=m; i+=2)
- if(vis[i]==0)
- cnt++;
- return cnt;
- }
- int main()
- {
- #ifndef Brain_FUCK
- freopen("input.txt","r",stdin);
- freopen("out.txt","w",stdout);
- #endif
- int n;
- cin>>n;
- if(n<2)cout<<"0"<<endl;
- else if(n==2)cout<<"1"<<endl;
- else
- {
- cout<<seive(n)<<endl;
- }
- }
Add Comment
Please, Sign In to add comment