Решето Эратосфена — алгоритм нахождения всех простых чисел до некоторого целого числа N, который приписывают древнегреческому математику Эратосфену Киренскому.
Название алгоритма говорит о принципе его работы, то есть решето подразумевает фильтрацию, в данном случае фильтрацию всех чисел за исключением простых. По мере обработки массива чисел нужные числа (простые) остаются, а ненужные (составные) исключаются.
Сама проблема получения простых чисел занимает ключевое место в математике, на ней основаны некоторые криптографические алгоритмы, например RSA.
Для нахождения всех простых чисел не больше заданного числа N нужно выполнить следующие шаги:
- Заполнить массив из N элементов целыми числами подряд от 2 до N.
- Присвоить переменной p значение 2 (первого простого числа).
Удалить из массива числа от p2 до N с шагом p. Это будут числа кратные p:
p2, p2+p, p2+2p и т. д.
- Найти первое оставшееся в массиве число, большее p, и присвоить значению переменной p это число.
- Повторять два предыдущих шага пока это возможно.
Все оставшиеся в массиве числа являются простыми числами от 2 до N
На рисунке проиллюстрирован алгоритм поиска простых чисел.
Числа, отмеченные серым цветом, являются удаленными.
Красным цветом обозначены простые числа.
Реализация на C++
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
using namespace std;
int main()
{
int n;
cout << "n= ";
cin >> n;
int* a = new int[n + 1];
for (int i = 0; i < n + 1; i++)
a[i] = i;
for (int p = 2; p < n + 1; p++)
{
if (a[p] != 0)
{
cout << a[p] << endl;
for (int j = p * p; j < n + 1; j += p)
a[j] = 0;
}
}
cin.get(); cin.get();
}Результат выполнения
