Простые числа.
Математики последующих поколений всячески совершенствовали «решето Эратосфена». Все усовершенствования сводились к уменьшению количества перебираемых чисел. Не смотря на это, поиск простых чисел оставался громоздкой процедурой, и чтобы не повторять её, стали выпускать таблицы простых чисел.
Первая таблица простых чисел была составлена в XVII веке и содержала числа от 2 до 743. А в середине XIX века в Венскую академию поступило 7 томов рукописных таблиц под названием «Великий канон делителей всех чисел, которые не делятся на 2,3, 5 и другие простые числа до 100330201». Выход «Канона» ускорил исследование простых чисел, и сразу появились первые результаты.
Расположение простых чисел в натуральном ряду вызывает вопросы. Видно, что чем дальше, тем реже встречаются простые числа, но появляются они в каком-то странном порядке – то попадаются огромные промежутки в натуральном ряду, сплошь состоящие из составных чисел, то простые числа практически соседствуют друг с другом (так называемые простые числа-близнецы, отличаются друг от друга на 2). Все же в этом беспорядке французский математик Бертран увидел такую закономерность (она называется «постулат Бертрана»): между любыми натуральными числами n и 2n-2, где n>3, обязательно находится хотя бы одно простое число. Например, если n=8, тогда 2n-2=14 и между ними находятся сразу два простых числа – 11 и 13.
Великий немецкий математик Карл Фридрих Гаусс в возрасте 15 лет нашел более фундаментальный (но и более сложный) закон распределения простых чисел среди натуральных. Но до сих пор простые числа таят в себе массу загадок. Закономерность их появления пока не найдена. Еще сложнее с простыми числами-близнецами.
Рассмотрим подробнее некоторые способы получения простых чисел. Решето Эратосфена – процедура, по крайней мере, скучная. Одним из первых предложил более интересный способ французский математик Пьер Ферма. Он рассмотрел числа вида 22n+1 
. Числа такого вида называют числами Ферма. Например, если n=3, то 2n=8 и 28+1=257-простое число. Конечно, формула Ферма не дает всех простых чисел, но сам Ферма и его современники были уверены в обратном – что все числа Ферма – простые. Опроверг это утверждение другой великий математик, Леонард Эйлер, заметив в 1732 году, что уже пятое число Ферма – составное: 225+1=641∙6700417. 
Ферма оказался неправ, но поиски простых чисел Ферма продолжаются и в наши дни на компьютере.
Эйлер предложил и свою формулу для получения простых чисел: n2+n+41, но очевидно, что при n=41 данна формула даст составное число, кратное 41. Менее очевидно, что при n=40, тоже получится составное число. Но это так.
Еще одна формула: n2-79n+1601 даёт простые числа при первых 79 значениях n, а при n=80 получается составное число.
В наше время математики тоже изыскивают новые способы получения простых чисел, а также их распознавания. Самое большое число, о котором на данный момент достоверно известно, что оно простое, содержит более 2 миллионов знаков.
Математики последующих поколений всячески совершенствовали «решето Эратосфена». Все усовершенствования сводились к уменьшению количества перебираемых чисел. Не смотря на это, поиск простых чисел оставался громоздкой процедурой, и чтобы не повторять её, стали выпускать таблицы простых чисел.
Первая таблица простых чисел была составлена в XVII веке и содержала числа от 2 до 743. А в середине XIX века в Венскую академию поступило 7 томов рукописных таблиц под названием «Великий канон делителей всех чисел, которые не делятся на 2,3, 5 и другие простые числа до 100330201». Выход «Канона» ускорил исследование простых чисел, и сразу появились первые результаты.
Расположение простых чисел в натуральном ряду вызывает вопросы. Видно, что чем дальше, тем реже встречаются простые числа, но появляются они в каком-то странном порядке – то попадаются огромные промежутки в натуральном ряду, сплошь состоящие из составных чисел, то простые числа практически соседствуют друг с другом (так называемые простые числа-близнецы, отличаются друг от друга на 2). Все же в этом беспорядке французский математик Бертран увидел такую закономерность (она называется «постулат Бертрана»): между любыми натуральными числами n и 2n-2, где n>3, обязательно находится хотя бы одно простое число. Например, если n=8, тогда 2n-2=14 и между ними находятся сразу два простых числа – 11 и 13.
Великий немецкий математик Карл Фридрих Гаусс в возрасте 15 лет нашел более фундаментальный (но и более сложный) закон распределения простых чисел среди натуральных. Но до сих пор простые числа таят в себе массу загадок. Закономерность их появления пока не найдена. Еще сложнее с простыми числами-близнецами.
Рассмотрим подробнее некоторые способы получения простых чисел. Решето Эратосфена – процедура, по крайней мере, скучная. Одним из первых предложил более интересный способ французский математик Пьер Ферма. Он рассмотрел числа вида 22n+1 . Числа такого вида называют числами Ферма. Например, если n=3, то 2n=8 и 28+1=257-простое число. Конечно, формула Ферма не дает всех простых чисел, но сам Ферма и его современники были уверены в обратном – что все числа Ферма – простые. Опроверг это утверждение другой великий математик, Леонард Эйлер, заметив в 1732 году, что уже пятое число Ферма – составное: 225+1=641∙6700417. Ферма оказался неправ, но поиски простых чисел Ферма продолжаются и в наши дни на компьютере.
Эйлер предложил и свою формулу для получения простых чисел: n2+n+41, но очевидно, что при n=41 данна формула даст составное число, кратное 41. Менее очевидно, что при n=40, тоже получится составное число. Но это так.
Еще одна формула: n2-79n+1601 даёт простые числа при первых 79 значениях n, а при n=80 получается составное число.
В наше время математики тоже изыскивают новые способы получения простых чисел, а также их распознавания. Самое большое число, о котором на данный момент достоверно известно, что оно простое, содержит более 2 миллионов знаков.