Решето Эратосфена — алгоритм нахождения всех простых чисел до некоторого целого числа 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
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();
}
Результат выполнения
Назад: Задачи и их решения
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
30
31
32
namespace erat1
{
class Program
{
static void Main(string[] args)
{
int n = 10000;
int len = n + 1;
int[] primes = new int[len];
for (int i = 0; i < len; i++)
primes[i] = i;
for (int i = 2; i < len; i++)
{
for (int j = i + 1; j < len; j++)
{
if (primes[j] == 0)
continue;
if (j % i == 0)
{
primes[j] = 0;
continue;
}
}
}
for (int i = 0; i < len; i++)
if(primes[i] != 0)
Console.WriteLine(primes[i]);
}
}
}
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
на 100000 не падает.
*/
#include<iostream>
using namespase std;
int main() {
int n;
vector<int> v;
cin >> n;
//заполняем вектор
for(int i = 0; i <= n; i++) v.push_back(i);
//обработка
for(int i = 2; i <= n; i++) {
for(int j = i + 1; j <= n; j++) {
if(v[j] == 0) continue;
if(j % i == 0) {
v[j] = 0;
continue;
}
}
if(i * i > n) break; // <== ОПТИМИЗАЦИЯ
}
//вывод на печать
for(int s : v) {
if(s != 0) cout << s << '\n';
}
return 0;
}