Untitled
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; }