Насколько известно, Эратосфен (276-194 до н. э.), библиотекарь из Александрии, был первым, кто в III веке до н. э построил таблицы простых чисел. Он придумал рационально легкий способ узнать, какие числа являются простыми на промежутке между двумя величинами, например 1 и 1000. Отставив в сторону число 1, которое не все математики считают простым, он искал первое простое число: число 2. Далее он вычеркивал все числа, кратные 2 (четные), которые, следовательно, уже не могли быть простыми. В списке незачеркнутых чисел он искал первое незачеркнутое число, которое автоматически было простым, в этом случае 3, и действовал тем же образом, зачеркивая все числа, кратные 3. Эратосфен продолжал эту процедуру, зная, что первое в его списке незачеркнутых чисел вновь будет простым (далее 5, 7,11...) и что именно оно определяет следующие числа, которые нужно удалить из списка (все кратные ему). С помощью этой процедуры он построил таблицы простых чисел. Этот метод получил название решето Эратосфена, поскольку таким образом строилась сеть, не включавшая числа, которые не могут быть простыми, точно так же, как сито золотоискателей помогает им находить самородки. Естественно, на каждом этапе ячейка решета Эратосферна меняется в размерах, поскольку процесс ускоряется.
Евклид также занимался простыми числами. В частности, его интересовал вопрос, бесконечно ли множество простых чисел. Мы можем находить простые числа в течение неопределенного времени или все же существует момент, когда они перестают появляться? Евклид нашел ответ на этот вопрос: множество простых чисел бесконечно. Древнегреческий математик выразил это, сказав, что количество простых чисел больше, чем любое число, которое можно задумать. Доказательство довольно элементарно и показывает мощь математического рассуждения, которое способно ответить на этот вопрос без необходимости искать каждый раз все большие простые числа.
Это утверждение доказывается от противного. Для начала предположим, что множество простых чисел конечно, то есть Р = {2, 3 pj..., pn} — это множество всех существующих простых чисел, и pn — наибольшее из них. Возьмем произведение всех их плюс один, то есть вычислим q = 2 · 3 · ... · рj, ... · pn + 1. Это число явно больше 1 + pn, и оно не может быть простым, поскольку тогда мы получили бы простое число, большее максимального pn. Тогда нужно предположить, что q — составное число. Так как любое составное число можно разложить на произведение простых, это означает, что все простые множители q находятся во множестве простых чисел Р. Следовательно, существует по крайней мере один элемент множества Р (обозначим его р), который является делителем q. Однако по построению pj также является делителем произведения 2 · 3 · ... · рj · ... · pn, поскольку рj — один из множителей этого произведения. Это означает, что р, является делителем g и g - 1, следовательно, оно должно быть делителем их разности, то есть 1, но ни одно простое число, большее 1, не является делителем 1. Мы пришли к противоречию. Вывод в том, что выбранное множество Р не является исчерпывающим, поскольку существуют простые числа, не принадлежащие ему, следовательно, множество простых чисел бесконечно.
С аргументацией Евклида исчезала возможность построить таблицу, в которой содержались бы все простые числа, и, следовательно, пропала возможность найти способ, который позволил бы описать их. Гораздо сильнее заключений Евклида результат, доказанный в 1737 году Эйлером, который гласит: сумма чисел, обратных простым, расходится. В виде математической формулы это выглядит следующим образом:
где р — простое число.
Очевидно, что из этого результата можно сделать вывод, что количество простых чисел бесконечно, поскольку для бесконечной суммы необходимо бесконечное количество слагаемых (и к этому выводу можно прийти с помощью одних только логических рассуждений).
Еще в юности Гаусс получил в подарок книгу, в которой содержался список нескольких миллиардов простых чисел, возможно полученных с помощью инструмента, напоминающего решето Эратосфена. Гаусс заметил, что числа появляются без всякой системы. Казалось почти невозможным определить порядок их распределения, или формулу, которая позволила бы находить их в бесконечном множестве натуральных чисел. Ученый, который смог определить орбиту небесных тел на основе немногих наблюдений, решил принять вызов. Мысль о том, что математики не могли найти правила распределения простых чисел, подхлестывала разум Гаусса. Он должен был найти порядок и регулярность там, где, казалось, есть только хаос.