Решето Эратосфена

Поиск простых чисел   10 июня 2012  Автор статьи:  

Решето Эратосфена — это алгоритм поиска всех простых чисел от 1 до какого-то фиксированного числа n.
Описание алгоритма:
Алгоритм состоит из пяти шагов.
На первом этапе выписываются все числа из диапазона от 1 до n.
.
Решето Эратосфена 1
На втором шаге выбирается переменная p, равная первому простому числу, т.е. 2.
На третьем этапе вычеркиваются все числа, кратные p, т.е. 2р, 3р, … , kp, где kp — первое число, превосходящее n.
.
Решето Эратосфена 2
На четвертом шаге переменной p присваивается следующее не зачеркнутое число.
И далее снова повторяются шаги три и четыре, до тез пор пока p меньше, чем n.
.
Решето Эратосфена 3
.
Решето Эратосфена 4

В итоге все не зачеркнутые числа — простые.
.
Решето Эратосфена 5

Научиться программировать

  • на Delphi

  • на Java

  • на C++