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

Решето́ Эратосфе́наалгоритм нахождения всех простых чисел до некоторого значения n.

Пример для n=20

Запишем натуральные числа начиная от 2 до 20 в ряд:

  2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20

Первое число в списке 2 — простое. Пройдём по ряду чисел, вычёркивая все числа кратные 2 (каждое второе, начиная с 22 = 4):

  2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20 

Следующее невычеркнутое число 3 — простое. Пройдём по ряду чисел, вычёркивая все числа кратные 3 (каждое третье, начиная с 32 = 9):

  2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20 

Следующее невычеркнутое число 5 — простое. Пройдём по ряду чисел, вычёркивая все числа кратные 5 (каждое пятое, начиная с 52 = 25). И т. д.

Необходимо провести вычёркивания кратных для всех простых чисел p, для которых p^2\le n. В результате все составные числа будут вычеркнуты, а невычеркнутыми останутся все простые числа. Для n=20 уже после вычёркивания кратных числу 3 все составные числа получаются вычеркнутыми.

 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home