Математика. Теория чисел. Решето Эратосфена.

Решето Эратосфена — метод нахождения простых не составных чисел из натурального ряда.

Разработан Эратосфеном Киренским (3 в. до н. э.).

Суть метода в отсеивании, фильтрации всех составных чисел, которые сам Эратосфен просто прокалывал на восковой табличке, потому и решето.

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

Составные числа — натуральные числа, большие единицы, не являющиеся простыми.

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

Алгоритм «Решето Эратосфена»

Итак в чем суть метода и как его применять.

Берем числовую последовательность натуральных чисел, начиная с 2.

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12…

И удаляем все числа кратные 2.

Для этого умножаем числа натурального ряда, по порядку на 2 и результат умножения вычеркиваем.

2×2=4, вычеркиваем 4,

2х3=6, вычеркиваем 6 и т.д.

Таким образом, исключаем все четные, больше 2.

Два  — простое число так как имеет, всего, два натуральных делителя 1 и 2.

Получаем.

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12…

Затем вычеркиваем числа кратные трем (умножаем на 3 все числа, так же, по порядку ):

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15…

Потом, вычеркиваем числа кратные пяти и т.д.

В итоге получим последовательность не зачеркнутых чисел, которые и есть простые.

Сам Эратосфен построил таблицу простых чисел до 1000.

Сейчас, найдены огромные простые числа, но процесс все еще идет.

Вот таблица первых 500 простых чисел.

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

Сама проблема получения простых чисел занимает ключевое место в математике, на ней основаны некоторые криптографические алгоритмы, например RSA.

Для нахождения всех простых чисел не больше заданного числа N нужно выполнить следующие шаги:

• Заполнить массив из N элементов целыми числами подряд от 2 до N.
• Присвоить переменной p значение 2 (первого простого числа).
• Удалить из массива числа от p² до N с шагом p (это будут числа кратные p: p², p²+p, p²+2p и т. д.).
• Найти первое неудаленное число в массиве, большее p, и присвоить значению переменной p это число.
• Повторять два предыдущих шага пока это возможно.

Все оставшиеся в массиве числа являются простыми числами от 2 до N

На рисунке проиллюстрирован алгоритм поиска простых чисел. Числа, отмеченные белым, являются удаленными.