Как же выбрать простые числа из состава всех целых чисел? Очевидно, что чем больше число, тем труднее решать вопрос, имеет ли оно делителей, меньших себя.
Когда зерна отделяют от примесей, применяют специальные сита с отверстиями, соответствующими размерам зерен.
Вот таким же примерно способом отделяют и простые числа от составных.
Требуется, предположим, выделить все простые числа в пределах от 2 до некоторого данного целого числа N. Выпишем сначала подряд все целые числа от 2 до N: 2, 3, 4, 5, …, N. Первое простое число 2. Подчеркнем его, а все числа, кратные двум (четные), зачеркнем. Первое из оставшихся чисел 3. Подчеркнем его как простое, а все числа «через два на третье» (то есть кратные трем) зачеркнем. Первое число из оставшихся теперь 5 (число 4 уже зачеркнуто). Подчеркиваем его как простое и зачеркиваем все числа «через четыре на пятое» (то есть кратные пяти) и так далее.
Такой способ постепенного «просеивания» чисел был придуман более чем 2000 лет назад греческим математиком Эратосфеном (276—196 гг. до н. э.). Эратосфен не зачеркивал числа, кратные 2, 3, 5 и т. д., а прокалывал дырочки над ними. Получалось нечто вроде решета, сквозь отверстия которого как бы просеивались составные числа, а простые оставались. Так до сих пор этот способ получения таблицы простых чисел и называется эратосфеновым решетом.
Способ, как видите, очень кропотливый, но вполне надежный.
Коллективными усилиями были постепенно выявлены и собраны в таблицу все простые числа в промежутке от 1 до 10 000 000 и частично дальше. Большую работу по составлению, тщательной проверке и изданию такой таблицы (издана в 1914 г.) выполнил американский математик Д. Лемер. Книга таблиц Лемера имеется в Московской государственной библиотеке им. В. И. Ленина; при желании с нее можно снять фотокопию.
Лет на 20 раньше Лемера составил таблицу простых чисел такого же объема (до 10 миллионов) математик самоучка Иван Михеевич Первушин и передал в дар отечественной Академии наук. В рукописном виде таблицы Первушина сохранились в архивах Академии наук и до наших дней, но опубликованы они не были.
Еще более титаническую вычислительную работу выполнил профессор Пражского университета Якуб Филипп Кулик. Он довел таблицы простых чисел до 100 миллионов (6 томов простых чисел и делителей составных). С 1867 г. таблицы Кулика являются собственностью библиотеки Венской Академии наук. Один из томов таблиц Я. Ф. Кулика бесследно исчез, как раз тот, который содержал числа в промежутке от 13-го миллиона до 23-го. Нелегко восстановить все утерянные простые числа и проверить громаду чисел, содержащихся в сохранившихся томах таблиц Кулика.
В тридцатых годах нашего столетия учитель средней школы Василий Антонович Голубев (Кувшиново) разработал для составления таблицы простых чисел систему «трафаретов», упрощающих вычислительную работу и почти исключающих возможность ошибок. При помощи своих «трафаретов» В. А. Голубев в 1939 г. выделил наименьшие простые делители всех чисел 11-го миллиона, а в 1941 г.— 12-го миллиона. Полученные таблицы, по традиции, он принес в дар Академии наук СССР.
Последовательность выделенных простых чисел продолжает расти. Известны отдельные очень большие простые числа и за пределами существующих таблиц. Так, например, И. М. Первушин в 3883 г. доказал, что число
261 – 1 = 2 305 843 009 213 693 951
есть число простое.
Длительное время число
2127—1 = 170 141 183 460 469 231 731687 303 715 884 105 727
было наибольшим известным простым числом. При помощи современных быстродействующих вычислительных машин в Лос-Анжелосе были получены колоссальные простые числа:
22281 –1, 24423—1 и др.
Математики, конечно, не могли мириться с тем, что простые числа добываются кустарными способами Им, естественно, хотелось создать такую общую формулу, которая в зависимости от всевозможных целых значений величины n давала бы только простые числа. Но, увы, такая формула оказалась «синей птицей». Ее никто так и не поймал до сих пор.
