fork download 
  1. #include <bits/stdc++.h>
  2. #define endl '\n'
  3. using namespace std;
  4. const int MAXN = 3e3;
  5. const int INF = 1e9;
  6. int n;
  7. vector<int> primes;
  8. bool is_prime[MAXN + 1];
  9. int pre[MAXN + 1];
  10. void sieve()
  11. {
  12.     // init
  13.     for (int i = 1; i <= MAXN; i++) is_prime[i] = true;
  14.     is_prime[1] = false;
  15.     // sieve of Eratosthenes
  16.     for (int i = 2; i * i <= MAXN; i++)
  17.     {
  18.         if (is_prime[i])
  19.         {
  20.             for (int j = 2; j * i <= MAXN; j++)
  21.             {
  22.                 is_prime[i * j] = false;
  23.             }
  24.         }
  25.     }
  26.     for (int i = 1; i <= MAXN; i++) if(is_prime[i]) primes.push_back(i);
  27. }
  28. bool is_almostNumber(int number)
  29. {
  30.     set<int> s;
  31.     while (number != 1)
  32.     {
  33.         if (s.size() > 2) return false;
  34.         for (int i = primes.size() - 1; i >= 0; i--)
  35.         {
  36.             if (number % primes[i] == 0)
  37.             {
  38.                 number /= primes[i];
  39.                 s.insert(primes[i]);
  40.                 break;
  41.             }
  42.         }
  43.     }
  44.     return (s.size() == 2);
  45. }
  46. void in()
  47. {
  48.     cin >> n;
  49. }
  50. void out()
  51. {
  52.     sieve();
  53.     int ans = 0;
  54.     for (int i = 1; i <= n; i++) if (is_almostNumber(i)) ans++;
  55.     cout << ans;
  56. }
  57. int main()
  58. {
  59.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  60.     in(); out();
  61. }
Success #stdin #stdout 0s 5304KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/xi377Y
language:
C++14 (gcc 8.3)
created:
14 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!