Алгоритмы нахождения простых чисел

Что такое простые числа

Определение 1

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

Пример 1

Например, 11 — это простое число. Его можно разделить только на 1 и 11. Деление простого числа на другое приводит к тому, что остается остаток, что называют простым числом. 13 ÷ 4 = 3 (остаток 1). Число, имеющее более двух множителей, называется составными числами. Наименьшее простое число равно 2, потому что оно делится само на себя и только на 1.

Пример 2

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) содержат возведение в степень. А нельзя ли для задания бесконечно многих простых чисел обойтись лишь сложением, вычитанием и умножением? Поищем ответ на этот вопрос.

Начнём с рассмотрения многочленов от одной переменной с натуральными коэффициентами; посмотрим, какие многочлены будут своими значениями иметь простые числа и в каком количестве.

Возьмём вначале многочлены первой степени (то есть линейные многочлены). Очевидно, что тривиальный многочлен x задаёт бесконечно много простых чисел, более того, все простые числа, но это неинтересный случай. А что можно сказать о многочлене ax+b (где a, b и x — натуральные числа)? Ясно, что если a и b имеют общий делитель, отличный от 1, то значение многочлена ax+b — число составное, кратное этому делителю. Случай же, когда a и b взаимно просты, гораздо менее очевиден.

Французский математик Лежандр (живший в XVIII веке) высказал гипотезу, что если a и b взаимно просты, то в арифметической прогрессии с первым членом b и разностью a встречается бесконечно много простых чисел. Эта гипотеза была доказана лишь в XIX столетии немецким математиком Леженом Дирихле.

Перейдём теперь к квадратным многочленам. Среди них есть «рекордсмены», например, многочлен x2 + x + 41 — его изучал ещё Леонард Эйлер. Этот многочлен принимает простые значения при x = 1, 2, …, 40. При x = 41 его значение — составное.

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

Интерес к представлению простых чисел в виде значений квадратных многочленов недавно возродился в связи с неожиданным наблюдением С. М. Улама 5. Начав на спирали из всех натуральных чисел (рис. 1) отмечать простые числа, Улам с удивлением обнаружил, что простые числа выстраиваются по диагоналям, образуя довольно длинные цепочки. (Докажите, что числа, расположенные вдоль какой-либо диагонали в пределах, ограниченных на рис. 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
Рис. 1.

Ещё более удивительным оказалось то, что закономерность эта наблюдалась и тогда, когда спираль была продолжена (с помощью компьютера) до больших чисел — на рис. 2 светлыми точками отмечены простые числа на спирали из первых 10 000 чисел. Узор, изображённый на рис. 2, получил название «скатерть Улама».


Рис. 2.

Чтобы отмеченная закономерность проявилась, не обязательно начинать спираль с единицы. Например, значения многочлена x2 + x + 41 выстраиваются по диагоналям у спирали, начинающейся с числа 41 (рис. 3).

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
Рис. 3.

Возможно, что читатели «Кванта», проявив изобретательность и должное терпение, смогут найти новые красивые «геометрические» закономерности расположения простых чисел среди множества всех чисел.

Феномен со стремлением простых чисел располагаться в цепочки вдоль диагоналей был обнаружен сравнительно недавно и ещё не получил какого-либо математического объяснения.

О представлении простых чисел с помощью многочленов от многих переменных мы скажем в конце статьи.

Решето Эратосфена

Это алгоритм поиска простых чисел. Для этого нужно:

  1. Записать все числа от 1 до n (например, записываются все числа от 1 до 100, если нужны все простые числа между ними);
  2. Вычеркнуть все числа, которые делятся на 2 (кроме 2);
  3. Вычеркнуть все числа, которые делятся на 3 (кроме 3);
  4. И так далее по порядку со всеми невычеркнутыми числами до числа 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:

23571113171923
29313741434753596167
717379838997101103107109
113127131137139149151157163167
173179181191193197199211223227
229233239241251257263269271277
281283293307311313317331337347
349353359367373379383389397401
409419421431433439443449457461
463467479487491499503509521523
541547557563569571577587593599
601607613617619631641643647653
659661673677683691701709719727
733739743751757761769773787797
809811821823827829839853857859
863877881883887907911919929937
941947953967971977983991997

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.

Докажите, что в арифметических прогрессиях 3, 7, 11, … и 5, 11, 17, … бесконечно много простых чисел.

2.

Каково множество тех многочленов, значения которых лежат вдоль диагонали, если спираль (см. рис. 1)

• начата с 1?

• начата с некоторого числа u?

• начата с некоторого числа u, и по спирали стоят члены арифметической прогрессии u, u + v, u + 2v, …?

3.

Теорема Вильсона утверждает, что если p — простое число, то (p–1)! + 1 делится на p. Как можно использовать этот результат, чтобы уменьшить число неизвестных в экспоненциальном многочлене R, задающем простые числа?

4.

Постройте экспоненциальный многочлен S(x, …, x), который задаёт множество полусумм простых чисел-близнецов, т.е. такой многочлен, что если S(x, …, x) > 0, то оба числа S(x, …, x) – 1 и S(x, …, x) + 1 являются простыми, и наоборот, если s – 1 и s + 1 — простые числа, то S(x, …, x) = s при некоторых x, …, x.

5.

Постройте экспоненциальный многочлен T(qx, …, x), такой, что

• если q — простое число, то существуют числа x, …, x такие, что T(qx, …, x) > 0;

• если q — простое число и T(qx, …, x) > 0, то T(qx, …, x) — простое число, следующее за q;

• если q не является простым числом, то всегда T(qx, …, x) ≤ 0.

Этот экспоненциальный многочлен даёт «формулу для следующего простого числа».

Теги

Популярные:

Последние:

Adblock
detector