Untitled

mail@pastecode.io avatar
unknown
abap
3 years ago
1.8 kB
3
Indexable
///  Bismillah Hir Rahmanir Rahim  /// 

#include<bits/stdc++.h>  
using namespace std; 
#include<set>
#include<map>
#define sp " "
#define ll long long
#define ull unsigned long long int 
#define nl endl
#define pb push_back
#define pf push_front 
#define vi vector<int>
#define vb vector<bool>
#define vll vector<long long >
#define vc vector<char>
#define FIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define time cerr << "Time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" sec"<<endl;

  vector <int> primes ;

   void sieve (int n ){
   
   vector <bool> check(n+1 , 1);
   check[0] = check[1] = 0 ; 


   for (int i = 2 ; i<=n ; i++ )
   {
    if (check[i])
    {
      for (int j = i*i ; j<=n ; j+=i)
      {
        check[j]=0;
      }
    }
   }

   
  for (int i = 0 ; i<=n ; i++)
  {
    if (check[i]) primes.pb(i);
  }
   }



   vi masud ;
   void irfan (int n )
   {
     int y = n ;
    for (int i = 0 ; primes[i]*primes[i]<=n ; i++)
    {
      if ( n % primes[i]==0)
      {
         int cnt = 0 ;
        while(n % primes[i] == 0)
        {
          n/=primes[i];
          cnt++;
        }
         
        masud.pb(primes[i]);
      }
   
    }
     


    if (n>1 && (y % n == 0))  masud.pb(n);
     
    
 

   }



int main ()
{
    FIO;
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    freopen("error.txt", "w", stderr);
    #endif
    
       int n ;
       cin   >>n ; 
       sieve(n);
       
         irfan(n);
          


      int k = 0 ; 
     for (int i = 2 ; i<=n ; i++)
     {
      irfan(i);
     
       if (masud.size() == 2 ) k++;
       masud.clear();
     }
  cout << k << nl; 
  time;
  return 0;
}