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

Решето Эратосфена // 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. $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}.

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

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