Решето Эратосфена

Решето Эратосфена // Merera Ru [3:49]

Решето Эратосфена // edyo.ru [4:12]

Решето Эратосфена. Способ получения простых чисел, не превосходящих заданное число N // Элементарная Математика [15:55]

Решето Эратосфена — алгоритм получения всех простых чисел на промежутке от 2 до заданного n. Заключается в том, что последовательно вычеркиваются составные числа, делящиеся на 2, 3, …, p, где p — максимальное простое число, меньшее или равное ${\sqrt {n}}$. После вычеркивания остаются все простые числа, не превышающие n. Алгоритм назван в честь древнегреческого математика Эратосфена, который его и изобрел.

Обозначения

n — натуральное число, n > 2;

k — количество простых чисел, не превышающих n;

p_i — i-ое простое число.

N_n = {1; 2; …; n} — множество натуральных чисел, не превосходящих n.

Алгоритмы получения простых чисел

Алгоритм 1

Входные данные: n.

1. b_j = 1 ∀j ∈ N_n, i = 2, k = 0.
2. Если b_i = 0, то идти к 6.
3. j = i².
4. Если j ≤ n, то b_j = 0, j = j + i, идти к 4.
5. k = k + 1, p_k = i.
6. i = i + 1.
7. Если i² ≤ n, то идти к 2.
8. Если b_i = 1, то k = k + 1, p_k = i.
9. i = i + 1.
10. Если i² ≤ n, то идти к 8.

Выходные данные: k; {p₁, p₂, …, p_k}.

Алгоритм 2

Входные данные: n.

1. Невозможно разобрать выражение (Ошибка преобразования. Сервер («https://wikimedia.org/api/rest_») сообщил: «Cannot get mml. Server problem.»): {\displaystyle b_{j}={\begin{cases}0,\ j=1{\text{ или }}j{\text{ — четное }}\forall j\in N_{n}/\{2\}\\1,\ j=2{\text{ или }}j{\text{ — нечетное }}\forall j\in N_{n}/\{1\}\\\end{cases}},\ i=3}
2. j = i².
3. Если j ≤ n, то b_j = 0, j = j + i, идти к 3.
4. i = i + 2.
5. Если i² ≤ n, то идти к 2.
6. k = 1, p₁ = 2, i = 3.
7. Если b_i = 1, то k = k + 1, p_k = i.
8. i = i + 2.
9. Если i ≤ n, то идти к 7.

Выходные данные: k; {p₁, p₂, …, p_k}.

Другие алгоритмы:

1. Наибольший общий делитель;
2. Наименьшее общее кратное;
3. Проверка кратности;
4. Деление по модулю;
5. Получение простых чисел;
6. Разложение на множители.