Получение простых чисел — различия между версиями

Версия 06:19, 14 февраля 2016

Получение простых чисел – это алгоритм, дающий набор простых чисел, не превышающих заданное.

Простые числа — это натуральные числа, которые делятся только на само себя и на единицу.

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

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

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

b_i — признак i-числа, который равен 1 если i-число простое, иначе - 0;

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

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

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

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

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

Заметим, что данные алгоритмы похожы на алгоритм оптимизированное Решето Эратосфена из Википедии.

@@ Строка 38: / Строка 38: @@
 *[[машина Поста]];
 *[[машина Тьюринга]];
-*[[составление перестановок]];
+*[[Составление перестановок|комбинаторные алгоритмы]];
-*[[составление лексикографических перестановок]];
-*[[составление сочетаний]];
-*[[составление лексикографических сочетаний]];
-*[[составление размещений]];
-*[[составление лексикографических размещений]];
-*[[составление разбиений]];
-*[[составление лексикографических разбиений]];
 *[[сортировка]];
 *[[алгоритм определения мест]].