Портал: Математика

Решето Эратосфена простой алгоритм для нахождения всех простых чисел до заданного максимального значения. Он работает, идентифицируя простые числа в порядке возрастания, удаляя из рассмотрения составные числа , кратные каждому простому числу . На этой анимации показан процесс поиска всех простых чисел не более 120. Алгоритм начинается с определения 2 как первого простого числа.а затем вычеркиваем каждое кратное от 2 до 120. Следующее доступное число, 3, является следующим простым числом, поэтому каждое кратное 3 вычеркивается. (В этой версии алгоритма число 6 не вычеркивается снова, поскольку оно было просто идентифицировано как кратное 2. Такая же оптимизация используется для всех последующих шагов процесса: при простом p , только кратные не менее p ² считаются вычеркнутыми, поскольку любые меньшие кратные уже должны были быть определены как кратные меньшим простым числам. Большие кратные, которые просто случайно уже вычеркнуты - например, 12 при рассмотрении кратных 3 - считаютсяснова зачеркнуто, потому что проверка таких дубликатов наложила бы ненужное снижение скорости на любую реальную реализацию алгоритма.) Следующее оставшееся число, 5, является следующим простым числом, поэтому его кратные числа вычеркиваются (начиная с 25); и так далее. Процесс продолжается до тех пор, пока в списке не останется больше составных чисел (т. Е. Когда квадрат следующего простого числа превысит указанный максимум). Остальные числа (здесь начиная с 11) все простые. Обратите внимание, что эту процедуру легко расширить, чтобы найти простые числа в любой заданной арифметической прогрессии . Этот древний алгоритм, одно из нескольких сит простых чисел , был приписан греческому математику Эратосфену ( ум.  Ок.  194 г.). До н.э. ) Никомаха в его работе I века ( CE ) Введение в арифметику . Другие более современные сита включают сито Сундарама (1934 г.) и сито Аткина (2003 г.). Основное преимущество ситовых методов - это отказ от дорогостоящих тестов на простоту (или, наоборот, тестов на делимость ). Их основным недостатком является их ограничение определенными диапазонами чисел, что делает этот тип метода неподходящим для приложений, требующих очень больших простых чисел, таких как криптография с открытым ключом .