Получение простых чисел

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

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

Обозначения

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

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

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

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

Алгоритмы получения простых чисел

Алгоритм 1

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

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

Алгоритм 2

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

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

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

Ссылки

• Участник:Logic-samara