ash_sinha

Untitled

Nov 2nd, 2022
686
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.56 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. vector<int> sieve()
  5. {
  6.     vector<int> sv(4000,0);
  7.     for(int i=2;i<4000;i++)
  8.     {
  9.         if(sv[i]==0){
  10.         for(int j=i;j<4000;j+=i)
  11.         if(sv[j]==0) sv[j]=i;
  12.         }
  13.     }
  14.     return sv;
  15. }
  16. int main()
  17. {
  18.     vector<int> sv=sieve();
  19.     int x,n,ans=0;
  20.     cin>>n;
  21.     for(int i=2;i<=n;i++){
  22.         x=i;
  23.         set<int> st;
  24.         while(x>1){
  25.             st.insert(sv[x]);
  26.             x/=sv[x];
  27.         }
  28.         if(st.size()==2) ans++;
  29.     }
  30.     cout<<ans<<"\n";
  31.     return 0;
  32. }
Advertisement
Add Comment
Please, Sign In to add comment