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

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

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

Обозначения

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

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}.

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

Другие алгоритмы:

• Наибольший общий делитель;
• Наименьшее общее кратное;
• Проверка кратности;
• Деление по модулю;
• Получение простых чисел;
• Разложение на множители.

Ссылки

• Википедия. Решето Эратосфена
• https://ru.wikipedia.org/wiki/Решето_Эратосфена
• Участник:Logic-samara