Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using namespace std;
- typedef long long ll;
- vector <ll> lp, p;
- ll n;
- void sieve() {
- lp.resize(n + 1, 0);
- for (int i = 2; i <= n; ++i) {
- if (!lp[i]) {
- lp[i] = i;
- p.push_back(i);
- }
- for (int j = 0; j < p.size() && p[j] <= lp[i] && i * p[j] <= n; ++j) {
- lp[i * p[j]] = p[j];
- }
- }
- }
- int main() {
- cin >> n;
- sieve();
- for (int i = 2; i <= n; ++i) {
- int cnt = 0;
- int j = i;
- int prev = -1;
- while (j > 1) {
- if (prev != lp[j]) ++cnt;
- prev = lp[j];
- j /= lp[j];
- if (cnt == 3) {
- cout << i << ' ';
- break;
- }
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement