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

Версия 13:35, 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}.

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

@@ Строка 36: / Строка 36: @@
 *[[метод математической индукции]];
 *[[схема примитивной рекурсии]];
+*[[рекурсия]];
 *[[машина Поста]];
 *[[машина Тьюринга]];