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

Решето Эратосфена − алгоритм

Греческий математик Эратосфен придумал метод отыскания простых чисел до определенного числа n. Записываем натуральные числа до n. Например:

Сначала вычеркиваем число 1, которая не является ни простым ни составным числом. Далее, начиная с числа 2 вычеркиваются все числа, больше 2 и кратные 2, т.е. 4, 6, 8, 10, 12:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12

Потом выбираем первое оставшиеся число после числа 2. Это 3. Начиная с 3 вычеркиваем все числа больше 3 и кратные числу 3. Это числа 6, 9, 12:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12

Продолжая далее, мы видим, что нет больше чисел, подлежащих вычеркиванию. Таким образом, все простые числа до 12 − это числа 2, 3, 5, 7, 11. Заметим, что процедуру можно остановить начиная с позиции числа 7, т.к. кратное числу 7 (2*7=14) больше числа 12.

Ниже мы представим алгоритм простроения таблицы простых чисел до n с помощью решето Эрастофена. Обозначим через P массив n элементов. Изначально все элементы массива (кроме первого) будут равны 1. После выполнения программы элементы массива P с значениями 1 будут соответствовать порядковому номеру простого числа в ряде натуральных чисел. Далее с помощью этого массива легко построить множество простых чисел до n.

Алгоритм нахождения индексов простых чисел до n:

1. Исходные данные n, k=2, P₀=0, P_i=1, i=2,....,n.
2. i=k.
3. i=i+k
4. Если i>n перейти к пункту 6
5. P_i=0. Перейти к пункту 3.
6. i=k+1
7. Если P_i=0, перейти к пункту 6
8. Если i≤n_i+n_i, то k=i. Перейти к пункту 2.
9. Конец.

После выполнения алгоритма мы получим индексы простых натуральных чисел. Далее используя цикл строим таблицу простых чисел до числа n, т.е. берем те числа из натурального ряда, для которых соответствующие значения P_i=1.