Anik_Akash

number of prime

Feb 13th, 2021 (edited)
304
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace    std;
  3.  
  4. #define mx           100005
  5.  
  6.  
  7. int seive(int m)
  8. {
  9.    
  10.     vector<int>prime;
  11.     bool vis[m]={0};
  12.    
  13.     int x=sqrt((int)m);
  14.     for(int i=3; i<=x; i+=2)
  15.     {
  16.         if(vis[i]==0)
  17.          {
  18.             for(int j=i*i; j<m; j+=2*i)
  19.                 vis[j]=1;
  20.         }
  21.     }
  22.     int cnt=1;
  23.  
  24.     for(int i=3; i<=m; i+=2)
  25.         if(vis[i]==0)
  26.             cnt++;
  27.     return cnt;
  28. }
  29.  
  30. int main()
  31. {
  32.    #ifndef Brain_FUCK
  33.         freopen("input.txt","r",stdin);
  34.         freopen("out.txt","w",stdout);
  35.     #endif
  36.    
  37.     int n;
  38.     cin>>n;
  39.     if(n<2)cout<<"0"<<endl;
  40.     else if(n==2)cout<<"1"<<endl;
  41.     else
  42.     {
  43.        cout<<seive(n)<<endl;
  44.     }
  45.    
  46. }
  47.  
  48.  
RAW Paste Data