- Эратосфена решето
-
Решето́ Эратосфе́на — простой алгоритм нахождения всех простых чисел до некоторого целого числа 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
4567891011121314151617181920Следующее невычеркнутое число 3 — простое. Пройдём по ряду чисел, вычёркивая все числа кратные 3 (каждое третье, начиная с 32 = 9):
2 3
4567891011121314151617181920Следующее невычеркнутое число 5 — простое. Пройдём по ряду чисел, вычёркивая все числа кратные 5 (каждое пятое, начиная с 52 = 25). И т. д.
Необходимо провести вычёркивания кратных для всех простых чисел p, для которых
. В результате все составные числа будут вычеркнуты, а невычеркнутыми останутся все простые числа. Для n = 20 уже после вычёркивания кратных числу 3 все составные числа получаются вычеркнутыми.
См. также
Примеры реализации
Turbo Pascal
prost:=1; //Подготовка параметра для нахождения простых чисел for i:=1 to n do //Цикл движения по массиву чисел begin //НАЧАЛО if p[i]=0 then continue else//Чтоб лишний раз не заходить в цикл inc(prost); //Увеличение параметра, j:=i; //Подготовка параметра вложенного цикла while j<=n do //Вложенный цикл для определения простых чисел if (p[j] mod prost=0) //Если остаток от деления элемента на следующее простое число равен 0.. and(p[j]<>0) //..и этот элемент не равен 0.. and(p[j]>prost) then //..и этот элемент больше параметра prost.. begin p[j]:=0; inc(j); end //..это СОСТАВНОЕ число, удаляем его из массива и ищем далее else inc(j); //иначе это простое число, и дальнейший поиск end; //КОНЕЦ
Wikimedia Foundation. 2010.