Эратосфен: решето и размер Земли

Человек по прозвищу «Бета»

Эратосфен Киренский (ок. 276 — ок. 194 до н. э.) с 245 года заведовал Александрийской библиотекой — крупнейшим научным учреждением древности — и был воспитателем наследника Птолемеев.

Современники прозвали его «Бета», второй буквой алфавита: он занимался всем сразу — математикой, астрономией, географией, филологией, хронологией, поэзией — и ни в чём, по их мнению, не был первым. Второе прозвище, «Пентатл» (пятиборец), звучало добрее и точнее. Сегодня видно, что в двух вещах он был именно первым, и обе стоят на этой карте.

Решето

Задача: выписать все простые числа до заданной границы.

Проверять каждое число по отдельности — плохая мысль: делителей много, работы много. Эратосфен предлагает обратное — не искать простые, а вычёркивать составные.

1. Выписываем $2,3,4,\dots,n$.
2. Берём первое невычеркнутое число, объявляем простым, вычёркиваем все его кратные.
3. Повторяем.

Проделаем до 50. Вычёркиваем кратные 2 (кроме самой двойки), потом кратные 3, потом 5, потом 7 — и останавливаемся, потому что $7^{2}=49\leqslant50$, а $11^{2}=121>50$. Остаётся:

$$2,\ 3,\ 5,\ 7,\ 11,\ 13,\ 17,\ 19,\ 23,\ 29,\ 31,\ 37,\ 41,\ 43,\ 47 .$$

Почему можно остановиться на $\sqrt n$. Если $m\leqslant n$ составное, то $m=ab$ с $a\leqslant b$, откуда $a\leqslant\sqrt m\leqslant\sqrt n$. Значит, у всякого составного числа есть делитель, не превосходящий $\sqrt n$, — и оно уже вычеркнуто.

Сколько это стоит. При просеивании по простому $p$ вычёркивается около $n/p$ чисел, значит всего операций примерно

$$\sum_{p\leqslant n}\frac{n}{p}=n\sum_{p\leqslant n}\frac1p\approx n\ln\ln n$$

— здесь использована оценка Эйлера для суммы обратных простых. Величина $\ln\ln n$ растёт до смешного медленно: при $n=10^{9}$ она меньше четырёх. Практически это линейное время, и до сих пор не придумано существенно лучшего способа получить все простые до границы.

Стоит различать две разные задачи, которые школьные учебники часто смешивают: выписать все простые до $n$ (решето Эратосфена, и оно оптимально) и проверить простоту одного большого числа (решето бесполезно, нужны тест Ферма, тест Люка — Лемера или алгоритм AKS). Для числа из 300 цифр решето непригодно принципиально: чисел до него больше, чем атомов во Вселенной.

От этого приёма пошло целое направление — решётные методы. Вигго БрунВигго Бруннорвежский математик · 1885–1978Превратил решето Эратосфена из способа выписывать простые в способ их считать — и доказал первое содержательное утверждение о простых близнецах: сумма обратных к ним сходится. в 1919 году научился обрезать вычёркивание так, чтобы контролировать ошибку, и получил первые результаты о простых-близнецах; СельбергАтле Сельбергнорвежский и американский математик · 1917–2007В оккупированной Норвегии в одиночку доказал, что положительная доля нулей дзета-функции лежит на критической прямой; потом получил элементарное доказательство теоремы о простых числах — и рассорился из-за… придал решету оптимальную форму; Линник в 1941-м придумал «большое решето». Двадцать два века спустя приём библиотекаря остаётся рабочим.

Размер Земли

Второй результат — измерение, которое до сих пор приводят как образец научного рассуждения.

Эратосфен знал, что в Сиене (нынешний Асуан) в полдень летнего солнцестояния солнце стоит точно в зените: оно освещает дно глубокого колодца, и вертикальный шест не даёт тени. В тот же момент в Александрии шест тень даёт, и угол между направлением на солнце и вертикалью составляет, по его измерению, «пятидесятую часть полного круга», то есть

$$\alpha=\frac{360^\circ}{50}=7^\circ12' .$$

Рассуждение: солнечные лучи практически параллельны, значит этот угол равен углу между Сиеной и Александрией, видимому из центра Земли. Расстояние между городами считалось равным 5000 стадиев. Значит

$$L=50\times5000=250\,000\ \text{стадиев}.$$

(Позже он изменил ответ на 252 000 — по-видимому, чтобы число делилось на 60 и удобно пересчитывалось в градусы: ровно 700 стадиев на градус.)

Насколько точно? Здесь нужна честность, которой популярные пересказы обычно избегают. Ответ зависит от того, чему равен стадий, а единого стадия в древности не было. При «олимпийском» стадии (185 м) получается $46\,250$ км — ошибка около 16 %. При «египетском» (157,5 м) — $39\,375$ км при истинных $40\,075$, то есть менее двух процентов. Какой стадий имел в виду Эратосфен, точно не известно, и утверждать «он ошибся на 1 %» нельзя.

Но метод от этого не страдает. Его достоинство — не в точности исходных данных, а в том, что величина планеты выведена из двух теней и одного расстояния, без единого шага за пределы Египта. Это, по-видимому, первое в истории измерение недоступного объекта косвенным путём — тот самый ход мысли, которым потом Бируни померит Землю с вершины горы, Лобачевский попробует измерить кривизну пространства по параллаксу звёзд, а астрономы — расстояния до галактик.

Остальное

Удвоение куба. Эратосфен построил механический прибор — мезолабий, — находивший два средних пропорциональных, то есть решавший делосскую задачу, к которой Гиппократ Хиосский свёл удвоение куба. Циркулем и линейкой это, как выяснится в 1837 году, невозможно; прибором — пожалуйста. Эратосфен, гордясь изобретением, поместил его описание на храмовой стеле вместе с эпиграммой собственного сочинения.

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

Хронология: он первым попытался расставить события греческой истории по единой шкале, отсчитывая от падения Трои.

Ослепнув в старости, он, по преданию, отказался от пищи и умер.

Следующая точка: снова Александрия — где числа перестанут быть отрезками и научатся записываться символами.