О решете Эратосфена - древнейшее решето простых чисел
Решето Эратосфена находит все простые числа до заданной границы без единого деления. Нужно только считать: после 2 вычеркните каждое второе число, после 3 - каждое третье и так далее. То, что останется, - простые числа. Спустя более двух тысяч лет это всё ещё один из самых быстрых способов их выписать.
Эратосфен Киренский
Эратосфен жил примерно с 276 по 194 год до н. э. и возглавлял великую Александрийскую библиотеку. Больше всего он известен тем, что измерил размер Земли по длине теней в двух городах. Решето названо в его честь, потому что Никомах из Герасы описал его как метод Эратосфена во «Введении в арифметику», написанном около 100 года н. э.
Как работает решето
Запишите числа от 2 до N. Первое число, 2, простое: вычеркните 4, 6, 8 и все остальные кратные 2. Следующее оставшееся число, 3, простое: вычеркните 9, 12, 15 и так далее. Продолжайте с 5, 7 и следующими оставшимися числами. У числа, которое ни разу не вычеркнули, нет меньшего делителя, значит, оно простое.
Остановка на квадратном корне
У каждого составного числа до N есть простой делитель, не превышающий квадратного корня из N. Поэтому, как только p² превысит N, вычёркивать больше нечего. Для простых чисел до 100 нужны только 2, 3, 5 и 7, а для 1000 - простые числа до 31.
Насколько оно быстрое?
Решету нужно около N log log N шагов, а это растёт лишь немного быстрее, чем само N. Компьютеры используют его до сих пор, часто по частям в виде сегментированного решета, чтобы выписывать простые числа вплоть до миллиардов. Чтобы проверить, простое ли одно большое число, быстрее другие методы.
Часто задаваемые вопросы
Кто придумал решето Эратосфена?
Оно названо в честь Эратосфена Киренского, греческого учёного III века до н. э. Самое древнее письменное описание принадлежит Никомаху из Герасы, около 100 года н. э.
Почему решето начинает вычёркивать с p²?
У каждого меньшего кратного p есть меньший простой делитель, поэтому меньшее простое число уже его вычеркнуло.
Сколько простых чисел меньше 1000?
Простых чисел меньше 1000 - 168. Самое большое из них - 997.
Сопутствующие инструменты
Решето Эратосфена
Посмотрите, как решето Эратосфена находит простые числа до 100, 200, 500 или 1000. Каждое простое число вычёркивает свои кратные своим цветом, шаг за шагом.
Спираль Улама
Постройте спираль Улама в браузере. Отметьте простые числа, прочитайте квадратичный многочлен каждой диагонали и откройте непрерывную серию из 40 простых чисел Эйлера.
Спираль Улама
Как спираль Станислава Улама 1963 года раскладывает целые числа на квадратной сетке, почему простые числа собираются на квадратичных диагоналях и где лежат сорок простых чисел Эйлера, если спираль начинается с 41.
Гипотеза Коллатца
Исследуйте задачу Коллатца 3n+1 в браузере. Проходите последовательности «градин», выращивайте геометрическое дерево Коллатца и приближайте непрерывный фрактал Коллатца.
Готовы попробовать?
Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.
Попробовать решето Эратосфена