blog.iakovlev.org
  26.07.2015

Простые числа

Простые числа называют "кирпичами" или "атомами" в здании математики. Основная теорема арифметики гласит:
любое натуральное число может быть разложено на простые множители, причем единственным образом.
Например, число 20 может быть представлено как
20 = 2*2*5
Эта теорема была сформулирована еще Евклидом. Евклидом же была доказана бесконечность числа простых чисел.

Одним из первых известных методов поиска простых чисел является т.н. решето Эратосфена, который жил в 3 веке до н.э. и работал в Александрийской библиотеке. Он заключается в том, что для того, чтобы найти все простые числа в диапазоне от 1 до N, нужно просеять все числа, меньше или равные квадратному корню из N. Он удобен и сейчас для нахождения т.н. малых простых чисел, т.е. чисел, меньших 10 миллиардов.
В первой тысяче натуральных чисел находится 168 простых чисел. С ростом чисел плотность появления простых чисел уменьшается, и на каком-то этапе среди тысячи подряд идущих натуральных чисел будет встречаться два, потом одно, а потом и ни одного простого числа, что произойдет, когда натуральное число будет состоять более чем из 100 цифр.
Появление простых чисел непредсказуемо. Они могут располагаться очень близко друг к другу - т.н. близнецы - либо очень долго не появляться. Близнецы с ростом чисел начинают встречаться все реже, но они продолжают встречаться и среди чрезвычайно больших чисел. Есть даже гипотеза, что их бесконечно много. В 2009 году были найдены самые большие простые числа-близнецы, каждое из которых состоит более чем из 100 тысяч цифр:
65516468355 * 2333333 - 1
65516468355 * 2333333 + 1
Также существует всего одна т.н. тройка простых чисел - 3,5,7 - и это доказанный факт.
Можно указать четыре последовательных простых числа - т.н. четверку - которые представляют ряд: p, p+2, p+6, p+8, например: 11, 13, 17, 19. Одна из самых далеких таких четверок начинается с числа p=2863308731. Существует гипотеза, что таких четверок бесконечно много.

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

Харди и Литлвуд высказали гипотезу, согласно которой каждое достаточно большое натуральное число, не являющееся квадратом, есть сумма квадрата и простого числа. Другая их гипотеза - уже - доказанная - гласит: каждое достаточно большое натуральное число есть сумма двух квадратов и простого числа.

Можно доказать, что в последовательности натуральных чисел можно найти сколь угодно большую последовательность подряд идущих чисел, в которой не будет ни одного простого числа. Для этого можно использовать факториал. Например, для того, чтобы найти 100 подряд идущих составных чисел, надо вычислить:
101! + 2
101! + 3
101! + 4
...
101! + 101

Мерсенн

Одним из первых математиков, описавших формулу для нахождения простых чисел, был Мерсенн. Это формула:
2p - 1
где p имеет одно из следующих значений:
2,3,5,7,13,17,19,31,67,127,257
Последнее число состоит из 77 цифр, и неизвестно, как Мерсенн доказал, что это число простое, хотя это не так. Только через 100 лет Эйлер смог доказать, что два в 31-й степени действительно простое число. В 1947 году список Мерсенна был проверен и уточнен:
2,3,5,7,13,17,19,31,61,89,107,127
Для того, чтобы число Мерсенна было простым, необходимо, чтобы показатель степени p был простым.
Известны на данный момент всего 49 чисел Мерсенна:
2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11 213, 19 937, 21 701, 23 209, 44 497, 86 243, 110 503, 132 049, 216 091, 756 839, 859 433, 1 257 787, 1 398 269, 2 976 221, 3 021 377, 6 972 593, 13 466 917, 20 996 011, 24 036 583, 25 964 951, 30 402 457, 32 582 657, 37 156 667, 42 643 801, 43 112 609, 57 885 161, 74 207 281
Последнее найденное число Мерсенна состоит из 22 миллионов разрядов, что на 5 миллионов больше предыдущего.

Пьер Ферма

В 1640 году Пьер Ферма сформулировал свою т.н. малую теорему, не оставив нам своего доказательства. Два числа называются взаимно простыми, если они не имеют общих делителей. Например, 8 и 27 - два взаимно простых числа, а 12 и 15 - нет. Малая теорема Ферма утверждает:
Пусть есть простое число p и другое число a, взаимно простое с p. Тогда разность двух чисел
(ap - a) - или что то же самое - (ap-1 - 1) - делится на p.
Эта теорема содержит необходимое, но не достаточное условие: если p - простое число, то условие выполняется, но выполнение условия не означает, что p будет простым обязательно. Эта теорема хорошо подходит для теста числа на простоту. Впервые официально малую теорему Ферма доказал Эйлер в 1736 году.
Натуральные числа вида
22n + 1
называются числами Ферма. Ферма предположил, что все числа, полученные таким образом, являются простыми. Но это оказалось не так - при n=5 получается составное число. В настоящее время известно, что только первые 5 чисел Ферма являются простыми.

В 1643 году Ферма предложил алгоритм для определения, является ли число простым, в основе которого лежит следующая теорема:
Если нечетное число N представимо в виде разности двух квадратов натуральных чисел только одним способом, то оно простое, если же более чем одним способом, то оно составное.
По этому способу к числу N нужно прибавлять квадраты всех целых чисел, меньших чем (N-1)/2, и каждый раз проверять, получится ли в сумме точный квадрат или нет. При этом способе нужно выполнять операцию сложения и иметь большую таблицу квадратов.
Такое разложение является необходимым, но недостаточным для того, чтобы сумма была простым числом.
Существует гипотеза, что простых чисел, являющихся суммами трех кубов натуральных чисел, существует бесконечно много.
Существует гипотеза, что простых чисел, являющихся суммами одного куба и числа 2, существует бесконечно много.
В 1951 году было доказано, что любое достаточно большое натуральное число является суммой восьми кубов натуральных чисел, из которых по крайней мере семь - кубы простых чисел.

Леонард Эйлер

Эйлер начал проявлять интерес к простым числам по приезду в Россию, в возрасте 20 лет. Этот интерес у него со временем вырос в открытие основных законов, которые сформировали новую науку - теорию чисел, И Эйлер считается основателем этой науки. Он нашел большое количество формул, которые позволяют получить большое количество простых чисел. Например, следующая формула генерирует простые числа для любых значений x, больших 0 и меньших q-2 :
x2 + x + q
С помощью этой формулы Эйлер нашел все простые числа для q=2,3,5,7,11,17.
В 1752 году Гольдбах во время переписки с Эйлером поставил гипотезу, согласно которой любое нечетное натуральное число можно представить в виде суммы трех простых чисел, на что Эйлер ответил, что имеет место следующий факт: любое четное число можно представить в виде суммы двух простых чисел. Первую гипотезу в 1937 году доказал Виноградов.

В 1738 году Эйлер дал первое доказательство малой теоремы Ферма. В 1758 году Эйлер дал еще одно ее доказательство следующим образом:
Пусть например для простоты мы возьмем небольшие числа - a=8, p=5. Рассмотрим ряд, состоящий из степеней числа a:
81, 82, 83, 84, 85, ... Если посмотреть на остатки от деления этих степеней на число p, то мы увидим, что их всего четыре:
3, 4, 2, 1, 3, 4, 2, 1 ..., которые в общем случае будут повторяться.
Каким бы ни было простое число p, число различных остатков от деления степеней числа a на число p будет на единицу меньше этого простого числа, что очевидно.
Теперь берем два числа из ряда степеней числа 8 - первое и пятое, и видим, что в обоих случаях остаток при делении этих степеней на 5 одинаковый и равен трем:
85 % 5 = 3
81 % 5 = 3
Отсюда:
85-1 % 5 = 1
Или
84 % 5 =1
и уже отсюда ->
( ap-1 - 1 ) - кратно p - что и требовалось доказать, причем p - простое число, a - любое натуральное целое число, не делящееся на p.
Ферма не оставил нам своего доказательства, но очевидно, что оно где-то рядом.

Малая теорема Ферма позволила Эйлеру установить целый ряд фактов:
Если целые числа a и b не делятся на простое число p=2m+1, то разность a2m - b2m делится на p.
Ни одно простое число вида 4n-1 не может быть делителем суммы двух взаимно-простых квадратов.
Все нечетные делители суммы двух взаимно-простых биквадратов могут быть только вида 8n+1

В 1758 году Эйлер написал труд "Арифметические статьи, доказанные новым способом", где впервые опубликовал функцию, доказанную абсолютно строго, впоследствии названную его именем, обозначающую число натуральных чисел, не превосходящих числа N и взаимно-простых с этим число N. Т.е. если натуральное число N записать в каноническом виде как произведение простых чисел:
N = p1x1p2x2p3x3...
то функция Эйлера может быть представлена в виде:
φ(N) = p1x1-1(p1-1)p2x2-1(p2-1)p3x3-1(p3-1)...
Можно пояснить на следующем примере: возьмем число 120 и приведем его к каноническому виду:
120 = 233151
Функция Эйлера для этого числа соответственно имеет вид:
φ(N) = 23-1*(2-1)*31-1*(3-1)*51-1*(5-1)=32
И действительно, всего насчитывается 32 натуральных числа , взаимно простых с 120 и не превосходящих 120:
1,7,11,13,17,19,23,29,31,37,41,43,47,49,53,59,61,67,71,73,77,79,83,89,91,97,101,103,107,109,113, 119

В этом же труде он доказал теорему, которая теперь носит имя Эйлера, по отношению к которой малая теорема Ферма превращается в частный случай. Теорема, доказанная Эйлером, звучит так: если имеется два взаимно простых числа x и N , то справедливо следующее:
xφ(N) ≡ 1(mod N)
Действительно, пусть например x=15, N=8. Функция φ(N)=4. Тогда
154 ≡ 1(mod 8)
Следующий код находит такие пары чисел x и N:
Код

Еще одна недоказанная теорема Ферма: Всякое простое число вида 4n+1 есть сумма двух квадратов - послужила Эйлеру толчком для написания специальной статьи, в которой он ее строго доказывает. Эйлер доказывает, что если такое число представляется в виде суммы двух квадратов единственным образом, то оно либо простое, либо удвоенно-простое , либо квадрат простого числа, либо вообще степень числа 2, в противном случае - составное.
В общем случае, рассматривая форму ax2 + by2, Эйлер формулирует критерий, с помощью котрого эта форма может генерировать простые числа: нужно рассматривать числа вида ab + y2, где y принимает значения меньшие, чем корень квадратный из 3ab, и взаимно-простые с ab.
Эйлер ввел понятие удобного числа: произведение ab называется удобным, если все числа, однозначно представимые формой abx2 + y2, являются или простыми, или удвоенными простыми, или квадратами простых, или степенями числа 2. Эйлер обнаружил 65 удобных чисел:
1.2.3.4.5.6.7.8.9.10.12.13.15.16.18.21,22,24,25,28,30,33,37,40,42,45,48,57,58,60,70,72,78,85,88,93,102,105, 112,120,130,133,165,168,177,190,210,232,240,253,273,280,312,330,345,357,385,408,462,520,760,840,1320,1365,1848.
Эйлер высказал гипотезу, что число удобных чисел конечно, и 1848 - последнее из них. Эта гипотеза не доказана до сих пор.

Если p - простое число, то квадратичным вычетом для числа p называется каждое число r, для которого существует целое число x, такое, что число x2 - r делится на p. Другими словами, целое число r называется квадратичным вычетом для p, если существует квадрат целого числа, дающий при делении на p такой же остаток, что и r.

В 1772 году Эйлер открыл еще один фундаментальный закон теории чисел - т.н. квадратичный закон взаимности. В современной трактовке этот закон гласит: если хотя бы одно из двух простых чисел p и q имеет вид 4n+1, то q есть квадратичный вычет p тогда и только тогда, когда и p есть квадратичный вычет q, а если p и q оба имеют вид 4n+3, то q есть квадратичный вычет p тогда, когда p есть невычет q, и наоборот.

Гаусс

Гаусс ввел в обиход функцию π(x), которая выражает количество простых чисел, меньших чем x. Если взять отношение числа х к функции π(x)
х / π(x)
то можно заметить, что для первых 10 натуральных чисел это число равно примерно двум, для 100 - четырем, для 1000 - 6, для 10000 - 8, и т.д., т.е. видна логарифмическая зависимость. Гаусс сформулировал следующую гипотезу:
При больших х значения π(x) / х приближаются к 1 / ln(x)
Эта гипотеза была доказана примерно через 100 лет после ее появления.
Гаусс ввел в математику понятие модуля и заново сформулировал малую теорему Ферма:
Если p - простое число, то для любого натурального числа a справедливо равенство
ap ≡ a (mod p) , или, что то же самое : (ap - a) кратно p

Риман

В свое время Эйлер, изучая гармонические ряды, ввел понятие дзета-функции:

Эйлер установил связь между этой функцией и простыми числами:

Риман поставил задачу - исследовать гипотезу Гаусса с помощью дзета-функции Эйлера и вывел свою собственную дзета-функцию:

Вторая часть этой функции, бесконечное произведение, распространяется на все простые числа p
Риман сформулировал гипотезу, что все нетривиальные нули дзета-функции лежат на прямой x = 1/2, которая проходит сквозь дзета-функцию. Если эта гипотеза верна, то все простые числа распределены регулярно, точнее, насколько это возможно регулярно. Это означает, что распределение простых чисел основано на определенном правиле, а не на чистой случайности. Позже было доказано, что на этой прямой расположено бесконечное число нулей дзета-функции. Гипотеза Римана не доказана до сих пор.

Алгоритмы

На данный момент существуют различные алгоритмы, с помощью которых можно получать простые числа.
Например, теорема Вильсона говорит, что p является простым числом тогда и только тогда, когда выполняется условие:
(p - 1)! ≡ -1 (mod p)
Формула Эйлера для получения 40 первых простых чисел:
x2 + x + 41
41-е число в этом ряду является уже составным. Существует гипотеза, что этот квадратный многочлен генерирует бесконечно много простых чисел.
Аналогичная формула x2 - 79x + 1601 дает простые числа для первых 80 натуральных чисел.

Самая длинная известная цепочка простых чисел в арифметической прогрессии содержит 19 членов; разность прогрессии — 4 180 566 390; первый член — 8 297 644 387. 20-й член будет составным, а дальше начинается чередование простых и составных чисел. Цепочка была найдена Притчардом в 1985 году.
Эту прогрессию можно использовать для генерации больших простых чисел, подставив ее разность прогрессии в общеизвестную формулу n-го члена арифметической прогрессии.

Существует бесконечно много простых чисел вида x2 + y2. Существует бесконечно много простых чисел вида x2 + y2 + 1. Существует бесконечно много простых чисел вида x2 + y2 + z2 + 1.

В настоящее время большинство известных очень больших простых чисел являются числами Мерсенна:
2n - 1

Для простых чисел-близнецов существует закономерность: пусть p1 и p2 - два простых числа-близнеца. Пусть n = p1 * p2
Пусть σ(n) - сигма-функция - сумма делителей числа n, включая n. Пусть φ(n) - фи-функция - равна числу чисел, взаимно простых с n и меньших, чем n.
Тогда для этих чисел-близнецов должно выполняться условие: σ(n) * φ(n) = (n-3)*(n+1)

Брун в 1920 году показал, что если в последовательности простых чисел оставить только пары-близнецы, функция π(x) для такой последовательности может быть вычислена по формуле π(x) = 100x / ln2(x) Так, π(109) = 3424506
Он же доказал, что ряд величин, обратных числам-близнецам, сходится к величине, равной 1.9021...


Вообще, существует доказанная теорема: Никакая целая рациональная функция от х с целыми коэффициентами не может для всякого натурального значения х равняться простому числу

Для проверки числа на простоту самым известным алгоритмом является решето Эратосфена, которое теряет эффективность для больших чисел.
Малая теорема Ферма дает необходимое, но не достаточное условие на простоту.
На сегодняшний день существует два типа алгоритмов проверки на простоту: детерминированный полиномиальный и вероятностный полиномиальный. Первый метод точный, но требует больше времени, второй быстрый, но существует небольшая вероятность ошибки. Ко второму типу относится алгоритм Миллера-Рабина с вероятностью ошибки, начиная от 1/1050. Второй тип проверки в основном и используется.

Также простые числа можно вычислять с помощью арифметических прогрессий вида:
1, 5, 9, 13, 17 ...
3, 7, 11, 15, 19 ...
Первая прогрессия состоит из чисел вида 4x + 1, вторая - 4x - 1. В обоих прогрессиях имеется бесконечно много простых чисел. То же самое можно сказать про 6x + 1 и 6x - 1. Вообще, прогрессия общего вида ax + b также имеет бесконечно много простых чисел, что было доказано Дирихле в 1836 году. Необходимо и достаточно, чтобы первый член и разность такой арифметической прогрессии не имели общего делителя.

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

Одна из самых длинных прогрессий, в которой простые числа идут подряд, начинается с числа 23143 и разностью 30030, первые 12 чисел этой прогрессии являются простыми числами. Доказано Кантором, что если нам нужно получить арифметическую прогрессию, первые 100 членов которой являются простыми числами, разность такой прогрессии должна состоять из нескольких десятков цифр.

Существует гипотеза, что имеется бесконечно много простых чисел вида x2 + 1, что до сих пор не доказано. Уравнение вида ax2 + bxy + cy2, в котором коэффициенты a, b, c взаимно просты, генерирует бесконечно много простых чисел, что было доказано Дирихле.

В 1830 году Шерк доказал, что каждое простое число можно представить в виде комбинации из ряда предыдущих простых чисел:
p2n = 1 ± p1 ± p2n ± ... ± p2n-2 + p2n-1
Например, 13 = 1+2-3-5+7+11

Существует гипотеза, что существует бесконечно много натуральных чисел n , для которых можно вычислить простое число по формуле :
pn = ( pn-1 + pn+1 ) / 2 , например, для n= 240, 273 ...

В книге Серпинского "Что мы знаем о простых числах", изданной у нас еще в 1963 году, приводился такой факт, что на момент написания книги было известно всего два простых числа, состоящих из одних единиц - это 11 и число из 23 единиц. Сейчас программа, написанная на питоне, за минуту находит несколько таких простых чисел, например, состоящее из 317 единиц, из 1031 единицы. Кстати, число единиц в таком простом числе также должно быть простым числом.

Теорема Лагранжа
Если p - простое число, а многочлен
f(x) = a0xn + a1xn-1 + ... + an-1x + an
имеет степень n>1 с целыми коэффициентами, где коэффициент a0 при высшей степени x не делится на p, то среди чисел
x=0,1,2,3...p-1
существует не более n таких, для которых число f(x) делится на p.

Теорема Вильсона
Является частным случаем теоремы Лагранжа.
Для каждого простого числа p число (p-1)! + 1 делится на p.
Из чего вытекает, что для того чтобы натуральное число n было простым, необходимо и достаточно, чтобы число (n-1)! + 1 делилось на n.

Теорема Лейбница
Вытекает из теоремы Вильсона
Для того чтобы натуральное число n было простым, необходимо и достаточно, чтобы число (n-2)! - 1 делилось на n.

Уравнение, связываюшее 3 важнейших функции теории чисел:
σ(m) + φ(n) = п * d(n)
где: σ(m) - сумма делителей числа n
φ(n) - функция Эйлера, равная количеству натуральных чисел, взаимно-простых с n
d(n) - число делителей числа n


Задачи

1 В книге Виноградова "Основы теории чисел", изданной в 1952 году, на странице 40 приведена задача: найти каноническое разложение числа 125! , т.е. нужно разложить это число на простые сомножители. Этот факториал состоит из 210 разрядов. Следующий код решает эту задачу. Число раскладывается на 30 простых делителей с разными степенями.
Код


2 Гипотеза Гольдбаха для четных чисел: каждое четное число может быть разложено на сумму двух простых чисел:
Код


3 Следующая задача взята из книги Дирихле "Лекции по теории чисел". Дано натуральное число n. Найти количество чисел, взаимно простых с n, и не превышающих n. Каждое натуральное число может быть разложено на простые сомножители:
n = aα * bβ * cγ * ...
Количество чисел, взаимно простых с n, в общем случае вычисляется по формуле:
(a-1)*aα-1 * (b-1)*bβ-1 * (c-1)*cγ-1 * ...
Например при n=60: 60 = 2*2*3*5
(2-1) * 2 * (3-1) * (5-1) = 16, т.е. существует 16 натуральных чисел, взаимно простых с 60 и меньших 60, и это числа: 1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59.
Код



4 Даны два взаимно простых числа a,b. Показать, что если произведение этих двух чисел есть квадрат, то и каждое из этих чисел является квадратом.
Код


5 Эта задача взята из книги: Серпинский, 250 задач по элементарной теории чисел.
Найти простые три числа p, q, r, для которых числа p(p+1), q(q+1), r(r+1) образуют возрастающую арифметическую прогрессию. Например: p=127, q=3697, r=5227 Кстати говоря, таких троек существует бесконечно много. В данном примере используется тот факт, что три числа вида n(n+1), (29n + 14)(29n+15), (41n + 20)()41n + 21) составляют арифметическую последовательность.
Код


6 Показать, что существует бесконечно много пар натуральных чисел m и n, таких, что, во-первых, числа m и n имеют одни и те же простые делители, и во-вторых, числа m+1 и n+1 также имеют одни и те же простые делители.
В коде используются формулы для нахождения таких пар: m=2k-2 и n=2k(2k-2)
Код


7 Следующая программа генерирует большие простые числа. Алгоритм работы следующий:
1 Генерируется исходная таблица простых чисел в пределах миллиона или миллиарда
2 Берем последнее простое число в найденом списке и умножаем его на 4 плюс 2 , результат умножаем на последнее число в начальном списке и прибавляем единицу - получаем искомое число N
3 Первая проверка - число N проверяем с помощью алгоритма Миллера-Рабина
4 Вторая проверка - число N проверяем на простые делители из все того же начального списка
На каждой итерации получается число с удвоенным количеством разрядов, и уже примерно на 7-й итерации можно получить простое число в тысячу знаков.
Вывод программы:
1 итерация 17 разрядов 15065350342811281
2 итерация 33 разрядов 285231202617538353166420535466421
3 итерация 66 разрядов 252512259076980992733523267029690470301694579910120585979067004321
... 
 7 итерация 1051 разряд 109921257801264751827334896002762792309332438376390813743974058934464844014745027587112466
 50388230044945714911848083094319471993751633968236612919366595170787329778356722055059379050918410650513118667039
 62760072267780485786654875017351537642234986249248634207369922859698832542303409282902260204359261039955835602026
 92827789357833419815991455647365610463566153100436949916743117580135736150014486868390630524281889462558602294365
 13460912408845592886531736587694942763327011306401351610757574929904271396040358030316735667355809952823075477524
 67312918347789528970735900693757401132838186447353232113814395609731416158526992757827232885108665416383466395370
 70120302871147693304332442610361318713113277737494103674006106729661620692374828838811944879924841457299782876762
 95932480513633809869145809804452711394258331301269242792664086167238737685634286607619432738110833909397530383138
 97278024310795339048873952772222750676220816465490870598865175614935865715814707667777455428048681536796749851174
 193916181436503577747450247026578104067896381297740880851
Код python

Код go

Еще Чебышев доказал, что между n и 2n-2 содержится хотя бы одно простое число. Из этой теоремы напрямую вытекает, что для любого натурального s существуют - как минимум - 3 простых числа, состоящих из s цифр. Я привел простое число, состоящее из 1051 цифры. Существуют еще как минимум два других простых числа, состоящих из 1051 цифры.
На самом деле - по теории - число простых чисел, состоящих из 1051 цифры, должно быть чудовищно велико - оно выражается числом, состоящим из 1048 цифр. Для его подсчета можно использовать формулу
x / ln(x)
Нужно применить эту формулу для x=101050 и x=101051 - вышенайденное простое число лежит между ними - и потом вычесть из второго результата первый.

Виноградов. Основы теории чисел

Дирихле. Лекции по теории чисел

Серпинский. 250 задач по элементарной теории чисел

Рибенбойм. Рекорды простых чисел

 Автор   Комментарий к данному блогу
bloks 
           Леонард Эйлер
x*x+x+q
q - простое число или все равно какое натуральное?
     2017-09-30 19:49:01
Яковлев Сергей 
           q - простое
     2017-10-01 15:28:47
bloks 
           1*1+1+7=9 - не получилось,
4*4+4+7=27 - опять не получилось
где я нарушаю условия формулы Эйлера?
     2017-10-05 04:59:34
Яковлев Сергей 
           А никто не сказал, что для всех x будут генерироваться простые числа

     2017-10-05 09:16:46
bloks 
           Судя по тексту
------------------
Например, следующая формула генерирует простые числа для любых значений x, больших 0 и меньших q-2 : 
x2 + x + q 
С помощью этой формулы Эйлер нашел все простые числа для q=2,3,5,7,11,17
------------------
Для любых х получается простые числа.
Интересно - а если ниже по тексту (в разделе про алгоритмы) проверить формулу
Х*Х+Х+41
Там дела не расходятся со словами?
     2017-10-05 19:03:15
Комментарий

Ваше имя:
Комментарий:
Оба поля являются обязательными