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

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

Определение 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})\), но об этом как-нибудь в другой раз.
• Любое число больше трёх можно представить в виде суммы двух простых (гипотеза Гольдбаха), но это не доказано.

Метод Марена Мерсенна

Метод простого числа Мерсенна — это специальный метод нахождения определенного вида простого числа, известный как простые числа Мерсенна. Название для этого метода происходит от французского монаха Марин Мерсенн, который первым определил его. Простые числа Мерсенна — это те, которые сводимы к виду 2ⁿ-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 столетии немецким математиком Леженом Дирихле.

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

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

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

Чтобы отмеченная закономерность проявилась, не обязательно начинать спираль с единицы. Например, значения многочлена x² + 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:

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.	Докажите, что в арифметических прогрессиях 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, …, xk ), который задаёт множество полусумм простых чисел-близнецов, т.е. такой многочлен, что если S(x, …, xk ) > 0, то оба числа S(x, …, xk ) – 1 и S(x, …, xk ) + 1 являются простыми, и наоборот, если s – 1 и s + 1 — простые числа, то S(x, …, xk ) = s при некоторых x, …, xk .
5.	Постройте экспоненциальный многочлен T(q, x, …, xm ), такой, что • если q — простое число, то существуют числа x, …, xm  такие, что T(q, x, …, xm ) > 0; • если q — простое число и T(q, x, …, xm ) > 0, то T(q, x, …, xm ) — простое число, следующее за q; • если q не является простым числом, то всегда T(q, x, …, xm ) ≤ 0. Этот экспоненциальный многочлен даёт «формулу для следующего простого числа».

Теги