Содержание материала
Что такое простые числа
Простые числа — натуральное число, имеющее ровно два различных натуральных делителя — единицу и самого себя. Другими словами, число x является простым, если оно больше 1 и при этом делится без остатка только на 1 и на x.
Например, 11 — это простое число. Его можно разделить только на 1 и 11. Деление простого числа на другое приводит к тому, что остается остаток, что называют простым числом. 13 ÷ 4 = 3 (остаток 1). Число, имеющее более двух множителей, называется составными числами. Наименьшее простое число равно 2, потому что оно делится само на себя и только на 1.
30 не является примером простого числа, потому что его можно разделить на 1,2,3,5,6,10,15,30. Таким образом, 30 является примером составного числа, поскольку оно имеет более двух факторов. Ноль, единица и числа меньше единицы не считаются простыми числами.
Видео
Разложение на простые множители
Любое натуральное число можно разложить на произведение простых, и с такой записью очень легко работать при решении задач. Разложение на простые множители еще называют факторизацией.
\[11 = 11 = 11^1\] \[100 = 2 \times 2 \times 5 \times 5 = 2^2 \times 5^2\] \[126 = 2 \times 3 \times 3 \times 7 = 2^1 \times 3^2 \times 7^1\]
Рассмотрим, например, такую задачу:
Условие: Нужно разбить \(N\) людей на группы равного размера. Нам интересно, какие размеры это могут быть.
Решение: По сути нас просят найти число делителей \(N\). Нужно посмотреть на разложение числа \(N\) на простые множители, в общем виде оно выглядит так:
\[N= p_1^{a_1} \times p_2^{a_2} \times \ldots \times p_k^{a_k}\]
Теперь подумаем над этим выражением с точки зрения комбинаторики. Чтобы «сгенерировать» какой-нибудь делитель, нужно подставить в степень \(i\)-го простого число от 0 до \(a_i\) (то есть \(a_i+1\) различное значение), и так для каждого. То есть делитель \(N\) выглядит ровно так: \[M= p_1^{b_1} \times p_2^{b_2} \times \ldots \times p_k^{b_k}, 0 \leq b_i \leq a_i\] Значит, ответом будет произведение \((a_1+1) \times (a_2+1) \times \ldots \times (a_k + 1)\).
Алгоритм разложения на простые множители
Применяя алгоритм проверки числа на простоту, мы умеем легко находить минимальный простой делитель числа N. Ясно, что как только мы нашли простой делитель числа \(N\), мы можем число \(N\) на него поделить и продолжить искать новый минимальный простой делитель.
Будем перебирать простой делитель от \(2\) до корня из \(N\) (как и раньше), но в случае, если \(N\) делится на этот делитель, будем просто на него делить. Причем, возможно, нам понадобится делить несколько раз (\(N\) может делиться на большую степень этого простого делителя). Так мы будем набирать простые делители и остановимся в тот момент, когда \(N\) стало либо \(1\), либо простым (и мы остановились, так как дошли до корня из него). Во втором случае надо еще само \(N\) добавить в ответ.
Напишем алгоритм факторизации:
Решение
За те же самые \(O(\sqrt{N})\). Итераций цикла while с перебором делителя будет не больше, чем \(\sqrt{N}\). Причем ровно \(\sqrt{N}\) операций будет только в том случае, если \(N\) — простое.
А итераций деления \(N\) на делители будет столько, сколько всего простых чисел в факторизации числа \(N\). Понятно, что это не больше, чем \(O(\log{N})\).
Разные свойства простых чисел*
Вообще, про простые числа известно много свойств, но почти все из них очень трудно доказать. Вот еще некоторые из них:
- Простых чисел, меньших \(N\), примерно \(\frac{N}{\ln N}\).
- N-ое простое число равно примерно \(N\ln N\).
- Простые числа распределены более-менее равномерно. Например, если вам нужно найти какое-то простое число в промежутке, то можно их просто перебрать и проверить — через несколько сотен какое-нибудь найдется.
- Для любого \(N \ge 2\) на интервале \((N, 2N)\) всегда найдется простое число (Постулат Бертрана)
- Впрочем, существуют сколь угодно длинные отрезки, на которых простых чисел нет. Самый простой способ такой построить — это начать с \(N! + 2\).
- Есть алгоритмы, проверяющие число на простоту намного быстрее, чем за корень.
- Максимальное число делителей равно примерно \(O(\sqrt[3]{n})\). Это не математический результат, а чисто эмпирический — не пишите его в асимптотиках.
- Максимальное число делителей у числа на отрезке \([1, 10^5]\) — 128
- Максимальное число делителей у числа на отрекзке \([1, 10^9]\) — 1344
- Максимальное число делителей у числа на отрезке \([1, 10^{18}]\) — 103680
- Наука умеет факторизовать числа за \(O(\sqrt[4]{n})\), но об этом как-нибудь в другой раз.
- Любое число больше трёх можно представить в виде суммы двух простых (гипотеза Гольдбаха), но это не доказано.
Метод Марена Мерсенна
Метод простого числа Мерсенна — это специальный метод нахождения определенного вида простого числа, известный как простые числа Мерсенна. Название для этого метода происходит от французского монаха Марин Мерсенн, который первым определил его. Простые числа Мерсенна — это те, которые сводимы к виду 2n-1, где n-простое число. Первые несколько чисел в этом методе являются 2, 3, 5, 7, 13, 17, 19, 31, 61, и 89. Долгое время метод простых чисел Мерсенна представлял собой тяжёлую работу, так как при переходе к более высоким простым числам он был очень трудоемким.

Однако, с появлением компьютеров, они теперь могли выполнять эти вычислительные вычисления, которые раньше делались людьми самым кропотливым и трудоемким образом. Мы определенно достигли более высоких простых чисел Мерсенна и простых чисел на общем уровне. Поиск простых чисел так же активен, как и другие численные поиски, выполняемые компьютерами. Другой числовой поиск, аналогичный движению простых чисел, заключается в добавлении десятичных разрядов к некоторым иррациональным числам, таким как пи (отношение длины окружности к диаметру). Однако непрерывный поиск следующего по величине простого числа существенно сложнее, чем поиск следующей цифры числа Пи.
Даже самые большие компьютеры (суперкомпьютеры) тратят значительное количество времени, чтобы проверить, является ли новое число (которое обычно ошеломляюще огромным) само по себе простым числом, и требуется еще больше времени, чтобы проверить, является ли число основным числом Мерсенна. По этой причине числа Мерсенна представляют большой интерес в области кибербезопасности и криптографии, особенно в отношении шифрования.
В августе 2008 года системный администратор UCLA Эдсон Смит нашел наиболее значимое простое число, известное на тот момент. Смит установил программное обеспечение для Great Internet Mersenne Prime Search (Gimps), проекта распределенных вычислений на добровольной основе. Это число было простым числом Мерсенна длиной 12 978 189 цифр. Чтобы дать представление о том, насколько он велик, на его написание уйдет почти два с половиной месяца, а в случае печати он растянется на 50 км!
Быстрое возведение в степень
Задача: > Даны натуральные числа \(a, b, c < 10^9\). Найдите \(a^b\) (mod \(c\)).
Мы хотим научиться возводить число в большую степень быстро, не просто умножая \(a\) на себя \(b\) раз. Требование на модуль здесь дано только для того, чтобы иметь возможность проверить правильность алгоритма для чисел, которые не влезают в int и long long.
Сам алгоритм довольно простой и рекурсивный, постарайтесь его придумать, решая вот такие примеры (прямо решать необязательно, но можно придумать, как посчитать значение этих чисел очень быстро):
- \(3^2\)
- \(3^4\)
- \(3^8\)
- \(3^{16}\)
- \(3^{32}\)
- \(3^{33}\)
- \(3^{66}\)
- \(3^{132}\)
- \(3^{133}\)
- \(3^{266}\)
- \(3^{532}\)
- \(3^{533}\)
- \(3^{1066}\)
Да, здесь специально приведена такая последовательность, в которой каждое следующее число легко считается через предыдущее: его либо нужно умножить на \(a=3\), либо возвести в квадрат. Так и получается рекурсивный алгоритм:
- \(a^0 = 1\)
- \(a^{2k}=(a^{k})^2\)
- \(a^{2k+1}=a^{2k}\times a\)
Нужно только после каждой операции делать mod: * \(a^0 \pmod c = 1\) * \(a^{2k} \pmod c = (a^{k} \pmod c)^2 \pmod c\) * \(a^{2k+1} \pmod c = ((a^{2k}\pmod c) \times a) \pmod c\)
Этот алгоритм называется быстрое возведение в степень. Он имеет много применений: * в криптографии очень часто надо возводить число в большую степень по модулю * используется для деления по простому модулю (см. далее) * можно быстро перемножать не только числа, но еще и матрицы (используется для динамики, например)
Асимптотика этого алгоритма, очевидно, \(O(\log c)\) — за каждые две итерации число уменьшается хотя бы в 2 раза.
Скатерть Улама
Формулы (8) и (9) содержат возведение в степень. А нельзя ли для задания бесконечно многих простых чисел обойтись лишь сложением, вычитанием и умножением? Поищем ответ на этот вопрос.
Начнём с рассмотрения многочленов от одной переменной с натуральными коэффициентами; посмотрим, какие многочлены будут своими значениями иметь простые числа и в каком количестве.
Возьмём вначале многочлены первой степени (то есть линейные многочлены). Очевидно, что тривиальный
Французский математик Лежандр (живший в XVIII веке) высказал гипотезу, что
Перейдём теперь к квадратным многочленам. Среди них есть «рекордсмены», например, многочлен
Доказано, что никакой многочлен (отличный, разумеется, от константы) не может иметь в качестве значений только простые числа, но до сих пор не известно, существует ли многочлен (кроме линейного), среди значений которого встречается бесконечно много простых чисел.
Интерес к представлению простых чисел в виде значений квадратных многочленов недавно возродился в связи с неожиданным наблюдением С. М. Улама 5. Начав на спирали из всех натуральных чисел (рис. 1) отмечать простые числа, Улам с удивлением обнаружил, что простые числа выстраиваются по диагоналям, образуя довольно длинные цепочки. (Докажите, что числа, расположенные вдоль
197 | 196 | 195 | 194 | 193 | 192 | 191 | 190 | 189 | 188 | 187 | 186 | 185 | 184 | 183 |
198 | 145 | 144 | 143 | 142 | 141 | 140 | 139 | 138 | 137 | 136 | 135 | 134 | 133 | 182 |
199 | 146 | 101 | 100 | 99 | 98 | 97 | 96 | 95 | 94 | 93 | 92 | 91 | 132 | 181 |
200 | 147 | 102 | 65 | 64 | 63 | 62 | 61 | 60 | 59 | 58 | 57 | 90 | 131 | 180 |
201 | 148 | 103 | 66 | 37 | 36 | 35 | 34 | 33 | 32 | 31 | 56 | 89 | 130 | 179 |
202 | 149 | 104 | 67 | 38 | 17 | 16 | 15 | 14 | 13 | 30 | 55 | 88 | 129 | 178 |
203 | 150 | 105 | 68 | 39 | 18 | 5 | 4 | 3 | 12 | 29 | 54 | 87 | 128 | 177 |
204 | 151 | 106 | 69 | 40 | 19 | 6 | 1 | 2 | 11 | 28 | 53 | 86 | 127 | 176 |
205 | 152 | 107 | 70 | 41 | 20 | 7 | 8 | 9 | 10 | 27 | 52 | 85 | 126 | 175 |
206 | 153 | 108 | 71 | 42 | 21 | 22 | 23 | 24 | 25 | 26 | 51 | 84 | 125 | 174 |
207 | 154 | 109 | 72 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 83 | 124 | 173 |
208 | 155 | 110 | 73 | 74 | 75 | 76 | 77 | 78 | 79 | 80 | 81 | 82 | 123 | 172 |
209 | 156 | 111 | 112 | 113 | 114 | 115 | 116 | 117 | 118 | 119 | 120 | 121 | 122 | 171 |
210 | 157 | 158 | 159 | 160 | 161 | 162 | 163 | 164 | 165 | 166 | 167 | 168 | 169 | 170 |
211 | 212 | 213 | 214 | 215 | 216 | 217 | 218 | 219 | 220 | 221 | 222 | 223 | 224 | 225 |
Ещё более удивительным оказалось то, что закономерность эта наблюдалась и тогда, когда спираль была продолжена (с помощью компьютера) до больших чисел — на рис. 2 светлыми точками отмечены простые числа на спирали из первых 10 000 чисел. Узор, изображённый на рис. 2, получил название «скатерть Улама».

Чтобы отмеченная закономерность проявилась, не обязательно начинать спираль с единицы. Например, значения многочлена
57 | 56 | 55 | 54 | 53 |
58 | 45 | 44 | 43 | 52 |
59 | 46 | 41 | 42 | 51 |
60 | 47 | 48 | 49 | 50 |
61 | 62 | 63 | 64 | 65 |
Возможно, что читатели «Кванта», проявив изобретательность и должное терпение, смогут найти новые красивые «геометрические» закономерности расположения простых чисел среди множества всех чисел.
Феномен со стремлением простых чисел располагаться в цепочки вдоль диагоналей был обнаружен сравнительно недавно и ещё не получил
О представлении простых чисел с помощью многочленов от многих переменных мы скажем в конце статьи.
Решето Эратосфена
Это алгоритм поиска простых чисел. Для этого нужно:
- Записать все числа от 1 до n (например, записываются все числа от 1 до 100, если нужны все простые числа между ними);
- Вычеркнуть все числа, которые делятся на 2 (кроме 2);
- Вычеркнуть все числа, которые делятся на 3 (кроме 3);
- И так далее по порядку со всеми невычеркнутыми числами до числа n (после 3 это 5, 7, 11, 13, 17 и т. д.).
Те числа, которые не будут вычеркнуты в конце этого процесса, являются простыми.
Как определить простые числа
Сначала попробуйте разделить его на 2 и посмотреть, получится ли целое число. Если да, то оно не может быть простым числом. Если вы не получите целое число, затем попробуйте разделить его на простые числа: 3, 5, 7, 11 (9 делится на 3) и так далее, всегда делясь на простое число.
8 простых чисел до 20: 2, 3, 5, 7, 11, 13, 17 и 19.
Первые 10 простых чисел — это 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.
Таблица простых чисел до 1000:
2 | 3 | 5 | 7 | 11 | 13 | 17 | 19 | 23 | |
29 | 31 | 37 | 41 | 43 | 47 | 53 | 59 | 61 | 67 |
71 | 73 | 79 | 83 | 89 | 97 | 101 | 103 | 107 | 109 |
113 | 127 | 131 | 137 | 139 | 149 | 151 | 157 | 163 | 167 |
173 | 179 | 181 | 191 | 193 | 197 | 199 | 211 | 223 | 227 |
229 | 233 | 239 | 241 | 251 | 257 | 263 | 269 | 271 | 277 |
281 | 283 | 293 | 307 | 311 | 313 | 317 | 331 | 337 | 347 |
349 | 353 | 359 | 367 | 373 | 379 | 383 | 389 | 397 | 401 |
409 | 419 | 421 | 431 | 433 | 439 | 443 | 449 | 457 | 461 |
463 | 467 | 479 | 487 | 491 | 499 | 503 | 509 | 521 | 523 |
541 | 547 | 557 | 563 | 569 | 571 | 577 | 587 | 593 | 599 |
601 | 607 | 613 | 617 | 619 | 631 | 641 | 643 | 647 | 653 |
659 | 661 | 673 | 677 | 683 | 691 | 701 | 709 | 719 | 727 |
733 | 739 | 743 | 751 | 757 | 761 | 769 | 773 | 787 | 797 |
809 | 811 | 821 | 823 | 827 | 829 | 839 | 853 | 857 | 859 |
863 | 877 | 881 | 883 | 887 | 907 | 911 | 919 | 929 | 937 |
941 | 947 | 953 | 967 | 971 | 977 | 983 | 991 | 997 |
2 — наименьшее простое число. Это также единственное четное простое число — все остальные четные числа могут быть разделены сами по себе на 1 и 2, что означает, что у них будет, по крайней мере, 3 фактора.
Один из самых известных математиков классической эпохи, Евклид, записал доказательство того, что не существует самого большого простого числа. Самое большое известное простое число (по состоянию на ноябрь 2020 года) составляет 282 589 933-1, число, которое имеет 24 862 048 цифр при записи в базе 10. До этого самым большим известным простым числом было 277 232 917-1, состоящее из 23 249 425 цифр.
За исключением 2 и 3, все остальные простые числа могут быть выражены в общей форме как 6n + 1 или 6n — 1, где n — натуральное число.
Чтобы определить, является ли число простым или составным, нужно решить пример на делимость в следующем порядке (от простого к сложному): 2, 5, 3, 11, 7, и 13. Если вы обнаружите, что число делится на одно из них, и вы знаете, что оно составное, не нужно выполнять остальные тесты.
Если число меньше 121 не делится на 2, 3, 5 или 7, оно простое; в противном случае оно составное.
Если число меньше 289 не делится на 2, 3, 5, 7, 11, или 13, это простое число; в противном случае оно составное.
Темы для размышлений
1. | Докажите, что в арифметических прогрессиях |
2. | Каково множество тех многочленов, значения которых лежат вдоль диагонали, если спираль • начата с 1? • начата с некоторого числа u? • начата с некоторого числа u, и по спирали стоят члены арифметической прогрессии u, u + v, |
3. | Теорема Вильсона утверждает, что если p — простое число, то |
4. | Постройте экспоненциальный многочлен |
5. | Постройте экспоненциальный многочлен • если q — простое число, то существуют числа • если q — простое число и • если q не является простым числом, то всегда Этот экспоненциальный многочлен даёт «формулу для следующего простого числа». |