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

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

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

Лекция 44: Решето Эратосфена // НОУ ИНТУИТ [24:42]

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

Обозначения

Введём обозначения:

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

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

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

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

Алгоритм 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. [math]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[/math]
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}.

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

• наибольший общий делитель;
• наименьшее общее кратное;
• проверка кратности;
• деление по модулю;
• решето Эратосфена;
• разложение числа на множители;
• система счисления;
• метод математической индукции;
• схема примитивной рекурсии;
• виды рекурсии;
• машина Поста;
• машина Тьюринга (вероятностная);
• комбинаторные алгоритмы;
• сортировка;
• алгоритм определения мест.