Решето Эратосфена
Решето Эратосфена — алгоритм получения всех простых чисел на промежутке от 2 до заданного n. Заключается в том, что последовательно вычеркиваются составные числа, делящиеся на 2, 3, …, p, где p — максимальное простое число, меньшее или равное [math]\sqrt n[/math]. После вычеркивания остаются все простые числа, не превышающие n. Алгоритм назван в честь древнегреческого математика Эратосфена, который его и изобрел.
Содержание |
[править] Обозначения
Введём обозначения:
n — натуральное число, n > 2;
k — количество простых чисел, не превышающих n;
pi — i-ое простое число.
[править] Алгоритмы получения простых чисел
[править] Алгоритм 1
Входные данные: n.
- bj = 1 ∀j ∈ Nn, i = 2, k = 0.
- Если bi = 0, то идти к 6.
- j = i².
- Если j ≤ n, то bj = 0, j = j + i, идти к 4.
- k = k + 1, pk = i.
- i = i + 1.
- Если i² ≤ n, то идти к 2.
- Если bi = 1, то k = k + 1, pk = i.
- i = i + 1.
- Если i² ≤ n, то идти к 8.
Выходные данные: k; {p1, p2, …, pk}.
[править] Алгоритм 2
Входные данные: n.
- [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]
- j = i².
- Если j ≤ n, то bj = 0, j = j + i, идти к 3.
- i = i + 2.
- Если i² ≤ n, то идти к 2.
- k = 1, p1 = 2, i = 3.
- Если bi = 1, то k = k + 1, pk = i.
- i = i + 2.
- Если i ≤ n, то идти к 7.
Выходные данные: k; {p1, p2, …, pk}.
[править] Другие алгоритмы
- наибольший общий делитель;
- наименьшее общее кратное;
- проверка кратности;
- деление по модулю;
- решето Эратосфена;
- разложение числа на множители;
- система счисления;
- метод математической индукции;
- схема примитивной рекурсии;
- виды рекурсии;
- машина Поста;
- машина Тьюринга (вероятностная);
- комбинаторные алгоритмы;
- сортировка;
- алгоритм определения мест.