Интернет магазин китайских планшетных компьютеров

Компьютеры - Решето Эратосфена

Решето Эратосфена — алгоритм нахождения всех простых чисел до некоторого целого числа n, который приписывают древнегреческому математику Эратосфену Киренскому.

Алгоритм

Для нахождения всех простых чисел не больше заданного числа n, следуя методу Эратосфена, нужно выполнить следующие шаги:

1. Выписать подряд все целые числа от двух до n.
2. Пусть переменная p изначально равна двум — первому простому числу.
3. Считая от p шагами по p, вычеркнуть из списка все числа от 2p до n кратные p
4. Найти первое не вычеркнутое число, большее чем p, и присвоить значению переменной p это число.
5. Повторять шаги 3 и 4 до тех пор, пока p не станет больше, чем n

Теперь все не вычеркнутые числа в списке — простые.

На практике, алгоритм можно несколько улучшить следующим образом. На шаге №3, числа можно вычеркивать, начиная сразу с числа p, потому что все составные числа меньше его уже будут вычеркнуты к этому времени. И, соответственно, останавливать алгоритм можно, когда p станет больше, чем n.

Можно показать, что сложность алгоритма составляет O операций в модели вычислений RAM, или O) битовых операций, при условии использования массивов с прямым доступом и вычеркивания каждого кратного числа за время O.