Решето Эратосфена — алгоритм нахождения всех простых чисел до некоторого целого числа 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();
}
Результат выполнения
переписал этот текст на собственный язык PPL, при n=100000 программа упала при значении 46349. Откомпилировал и запустил оригинал на cpp — тот же результат — последнее простое число 46349. проблема во внутреннем цикле, когда индекс выходит за границы массива. Нужен отлаженный код для проверки языка PPL
Видимо, это последнее простое число в 2-байтной разрядной сетке (до 65535)
// сделал исправления в вашем коде, не выходит за границы массива и не падает,
// написал на C#
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;
}
А если надо найти n-е по счёту число этим способом?
Мы же не знаем изначально, сколько чисел для просеивания надо брать?
Если делать частями, то мы не знаем, с какого места просеивать последующие "куски" выборок.
Просеивать последующие куски выборок нужно с начала
А как можно реализовать использование не всех чисел, а только нечетных, и среди нечетных уже искать простые?
Это уже реализовано в алгоритме
Не могу понять 8 рядок. Понимаю, что описывается массив. Подскажите, пожалуйста!
<span class="prog">n</span> — это число, до которого ищутся простые числа.
В строке 8 выделяется память под n+1 целое число
А как разложить число на простые множители по этому принципу?
Посмотрите здесь