А если серьёзно, то как-то не люблю заведомо неоптимальные функции.
Лучше уж тогда эратосфеном:
| C++ |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| #include <iostream>
#include <vector>
int next_true (std::vector<bool> & sieve, int pos) {
int i;
for (i = pos; i < sieve.size(); ++i) if (sieve[i] == true) return i;
return i;
}
void seed (std::vector<bool> & sieve) {
for (int i = 2; i < sieve.size(); i = next_true(sieve, i + 1))
for (int j = i * 2; j < sieve.size(); j += i) sieve[j] = false;
}
int main (int argc, char * const argv[]) {
int supremum;
std::cin >> supremum;
std::vector<bool> sieve(supremum, true);
sieve[0] = false;
sieve[1] = false;
seed(sieve);
for (int i = 2; i < sieve.size(); ++i) if (sieve[i]) std::cout << i << ' ';
return 0;
} |
|
