Решето чисел
Простые числа — «атомы» математики: любое натуральное число единственным образом раскладывается в их произведение (основная теорема арифметики). Решето Эратосфена — древнейший алгоритм поиска простых. Ему более 2200 лет, а лучшего для нахождения всех простых до N по сей день нет.
Эратосфен Киренский (~276–194 до н.э.) — греческий математик, поэт, географ и главный библиотекарь Александрийской библиотеки. Он первым измерил длину окружности Земли с ошибкой менее 2%, составил каталог из 675 звёзд и придумал этот алгоритм. Сам он назвал метод «просеиванием» (греч. κόσκινον — решето).
Почему начинаем с p²? Все меньшие кратные уже вычеркнуты предыдущими простыми — дублировать работу не нужно.
Сложность алгоритма — O(n · log log n) — практически линейная. Чтобы найти все простые до миллиона, нужно около 3,5 млн операций — в тысячи раз быстрее наивной проверки каждого числа на делители.
Простые числа становятся всё реже по мере роста N. Теорема о простых числах (1896, Адамар и де ла Валле-Пуссен):
Здесь π(N) — количество простых, не превышающих N. До 100 их 25, до 1000 — 168, до миллиона — 78 498.
Доказал Евклид ≈ 300 г. до н.э. Классическое доказательство от противного: допустим, простых конечно — p₁, p₂, …, pₖ. Рассмотрим число P = p₁·p₂·…·pₖ + 1. Оно не делится ни на одно pᵢ (остаток 1). Значит, у P есть простой делитель, которого нет в списке. Противоречие!
🏆 Наибольшее известное простое число (2024): 2¹³⁶ ²⁷⁹ ⁸⁴¹ − 1 — число Мерсенна, в нём более 41 миллиона цифр!