Advertisement
Guest User

Untitled

a guest
Jul 16th, 2019
101
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.63 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. typedef long long ll;
  7.  
  8. vector <ll> lp, p;
  9.  
  10. ll n;
  11.  
  12. void sieve() {
  13.     lp.resize(n + 1, 0);
  14.     for (int i = 2; i <= n; ++i) {
  15.         if (!lp[i]) {
  16.             lp[i] = i;
  17.             p.push_back(i);
  18.         }
  19.         for (int j = 0; j < p.size() && p[j] <= lp[i] && i * p[j] <= n; ++j) {
  20.             lp[i * p[j]] = p[j];
  21.         }
  22.     }
  23. }
  24.  
  25. int main() {
  26.     cin >> n;
  27.     sieve();
  28.     for (int i = 2; i <= n; ++i) {
  29.         int cnt = 0;
  30.         int j = i;
  31.         int prev = -1;
  32.         while (j > 1) {
  33.             if (prev != lp[j]) ++cnt;
  34.             prev = lp[j];
  35.             j /= lp[j];
  36.             if (cnt == 3) {
  37.                 cout << i << ' ';
  38.                 break;
  39.             }
  40.         }
  41.     }
  42.     return 0;
  43. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement