Представлен ряд задач, связанных с простыми числами — натуральными (целыми положительными) числами, большими 1, не имеющими других делителей, кроме самих себя и единицы.

Рассмотрим сначала такую задачу:

Задача 1. <Дано натуральное число n. Проверить, является ли оно простым>.

Метод решения этой задачи очевиден. Если n — четное, то оно не простое (составное), иначе следует проверить, являются ли делителем n числа 3, 5, 7,…,n/3 (проверять до n-1 и даже до n/2 нет необходимости), и если хотя бы для одного числа ответ будет положительным, то число n — составное. Заметим при этом, что число 2 — простое.

Задача 2. Даны натуральные числа a,b (a<=b). Получить все простые числа p, удовлетворяющие неравенствам a<=p<=b.

Задача 3. Найти 100 первых простых чисел.

Задача 4. Дано четное число n>2; проверить для этого числа гипотезу Гольдбаха. Эта гипотеза (по сегодняшний день не опровергнутая и пол-ностью не доказанная) заключается в том, что каждое четное n, большее двух, представляется в виде суммы двух простых чисел. Определить про-цедуру, позволяющую распознавать простые числа).

Для проверки гипотезы следует определить, имеются ли среди пар чисел 2 и n-2, 3 и n-

Задача 5. Дано натуральное число n. Выяснить, имеются ли среди n, n+1, …, 2n близнецы, т.е. простые числа, разность между которыми равна двум. (Определить процедуру, позволяющую распознавать простые числа).