// erastos.cpp: Решето Эратосфена для нахождения
// всех простых чисел, меньших заданного предела.
iinclude <iostream> iinclude <vector> #include <math.h>
using namespace std;
int main() { cout «
"To generate all prime numbers < N, enter N: ";
long N, i, sqrtN, count = 0, j;
cin >> N;
sqrtN = int(sqrt(N)) + 1;
vector<bool> S(N, true);
// Вначале все S[i] равны true.
// S[i] = false только и когда
//мы обнаруживаем, что i не есть простое.
for (i=2; i < sqrtN; i++) if (S[i])
for (int j=i*i; j<N; j+=i) S[j] = false;
for (i=2; i<N; i++)
if (S[i]) {j = i; count++;}
cout << "There are " « count
« " prime numbers less than N.\n"; cout « "Largest prime number less than N is "
« j << "." « endl; return 0; }
Ниже следует пример результатов работы этой программы, который показывает, что количество найденных простых чисел действительно может быть слишком большим для того, чтобы показать их все на экране:
То generate all prime numbers < N, enter N: 1000000 There are 78498 prime numbers less than N. Largest prime number less than N is 999983.
Время, которое потребовалось на выполнение примера, составило около 10 секунд на компьютере с процессором 80486; это показывает, что решето
Эратосфена позволяет очень быстро находить простые числа. Также этот пример показывает, что булевские векторы не только очень удобны, но и эффективны.
<< назад вперед >>