'''Получение простых чисел''' – это алгоритм, дающий набор всех простых чисел, не превышающих заданное.
'''Простые числа''' — это натуральные числа, имеющие которые делятся только два делителя: 1 и на само число (число 1 не считается простым числом, то есть простые числа — это 2, 3, 5, 7, 11,…)себя и на единицу.
== Обозначения ==
Введём обозначения: '''n''' — натуральное число, '''n>2''';
'''k''' — количество простых чисел, не превышающих '''n''';
'''b<sub>i</sub>''' — признак '''i'''-числа, который равен 1 если '''i'''-число простое, иначе - 0;
'''p<sub>i</sub>''' — '''i'''-ое простое число.
== Алгоритм Алгоритмы получения простых чисел ===== Алгоритм 1 ===
Входные данные: '''n'''.
[[файл:ППЧ01.JPG]]
Выходные данные: '''k; {p<sub>1</sub>,p<sub>2</sub>,…,p<sub>k</sub>}; {b<sub>1</sub>, b<sub>2</sub>, …, b<sub>n</sub>}'''.* Заметим, что данный алгоритм похож на алгоритм === Алгоритм 2 ===Входные данные: '''оптимизированное Решето Эратосфенаn''' из Википедии.== Другие алгоритмы ==* [[наибольший общий делительфайл:ППЧ02.JPG]];* [[наименьшее общее кратное]];* [[проверка кратности]]Выходные данные: '''k;* [[деление по модулю]]{p<sub>1</sub>, p<sub>2</sub>, …, p<sub>k</sub>};{b<sub>1</sub>, b<sub>2</sub>, …, b<sub>n</sub>}'''.* [[получение простых чисел]];* [[разложение Заметим, что данные алгоритмы похожы на множители]];* [[составление перестановок]];* [[составление сочетаний]];* [[составление размещений]];* [[составление разбиений]];* [[сортировка]];* [[алгоритм определения мест]];'''оптимизированное Решето Эратосфена''' из Википедии.* == [[метод математической индукцииАлгоритмы в арифметике|Другие алгоритмы:]];==* [[схема примитивной рекурсии]];* [[система счисления]].{{Список ААлг}}
== Ссылки ==
* [[Участник:Logic-samara]]
[[Категория:Математика]][[Категория:Алгоритмы]]