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

Версия 06:48, 2 февраля 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}.

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

@@ Строка 18: / Строка 18: @@
 [[файл:ППЧ01.JPG]]
-Выходные данные: '''k; {p<sub>1</sub>, p<sub>2</sub>, …, p<sub>k</sub>}'''.
+Выходные данные: '''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'''.
@@ Строка 24: / Строка 24: @@
 [[файл:ППЧ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>}'''.
+Выходные данные: '''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>}'''.
 * Заметим, что данные алгоритмы похожы на алгоритм '''оптимизированное Решето Эратосфена''' из Википедии.
 == Другие алгоритмы: ==