второе число после 2
Теперь перейдем к минимальному незачеркнутому числу, в нашем случае к 3, и систематически отбросим все остальные числа, кратные 3:
Рис. 1.19. Теперь зачеркните каждое третье число после 3
Поскольку 4 уже было отброшено, далее мы переходим к 5 и зачеркиваем каждое пятое число после 5. Мы повторяем далее эту процедуру и переходим к минимальному числу n, которое еще не было устранено, и вычеркиваем все числа, расположенные через n после него:
Рис. 1.20. Наконец у вас останутся все простые числа из интервала от 1 до 100
Эта процедура прекрасна тем, что она совершенно механическая и не требует размышлений. К примеру, простое ли число 91? Если вы используете данный метод, то не нужно думать. 91 будет зачеркнуто, когда вы отбрасываете числа, кратные 7, ведь 91 = 7 × 13. На числе 91 зачастую происходит ошибка, потому что мы не стремимся учить таблицу умножения 7 до 13.
Эта систематическая процедура служит хорошим примером алгоритма, метода решения задачи путем выполнения заданного набора инструкций – так, по существу, устроена компьютерная программа. Именно этот алгоритм был открыт две тысячи лет назад в одном из центров математической мысли своего времени – в Александрии, которая располагается на территории современного Египта. Тогда Александрия была форпостом великой Греческой империи и славилась одной из лучших библиотек мира. В III в. до н. э. библиотекарь Эратосфен и придумал эту раннюю компьютерную программу для нахождения простых чисел.
Она называется решетом Эратосфена, потому что всякий раз, когда вы просеиваете группу составных чисел, вы как бы используете решето, у которого расстояние между прутьями равно достигнутому вами простому числу. Сначала расстояние между прутьями равно 2, затем 3, потом 5 и т. д. Единственный недостаток этого метода: он быстро становится неэффективным, если вы ищете все бо́льшие и бо́льшие простые числа.
Эратосфен не только отсеивал простые числа и приглядывал за сотнями тысяч папирусных и пергаментных свитков в библиотеке, но и вычислил радиус Земли, а также расстояние от Земли до Солнца и Луны. По его расчету, Солнце находилось в 804 000 000 стадиев от Земли – хотя непонятно, каким именно стадием он пользовался, что делает трудной оценку точности его вычислений. Какой стадион подразумевали бы мы: «Уэмбли» или что-то поменьше, вроде «Лофтус Роуд»?
Кроме расчетов Солнечной системы, Эратосфен нанес Нил на карту и дал первое правильное объяснение его разливов: они были обусловлены сильными дождями в его удаленных верховьях в Эфиопии. Он даже создавал поэтические произведения. Но, несмотря на всю его активность, друзья дали ему прозвище Бета, потому что он ни в чем не преуспел по-настоящему. Говорили, что он уморил себя голодом после того, как ослеп в старческом возрасте.
Вы можете использовать какую-либо настольную игру с числовыми полями для приведения решета Эратосфена в действие. Возьмите спагетти и кладите их кусочки на исключаемые