Решето Эратосфена для нахождения простых чисел
В последовательности чисел 2, 3, ..., n последовательно вычеркиваем каждое второе число после 2. Первое незачеркнутое число простое (3). Далее вычеркиваем каждое третье число после 3. Первое незачеркнутое число простое (5). Затем вычеркиваем каждое пятое число после 5 и т.д. до тех пор, пока не дойдем до числа, большего корня из n (известно, что если целое положительное число n, неравное 1, не делится ни на одно положительное простое число, не большее корня из n то оно простое). Все числа, которые остаются, простые. Такой метод нахождения простых чисел называется решетом Эратосфена.
Текст программы
!Воронков Михаил группа 1660
program eratosfen
implicit none
integer max/500000/, n(500000), m, lastN/2/, k
!Файл со списком простых чисел
open(1,file='simpleNum.txt')
!Формируем массив
n(1)=0
do k=lastN,max,1
n(k)=k
enddo
!Выбираем простые числа
do while(lastN<=max)
do while(n(lastN)==0 .and. lastN<=max)
lastN=lastN+1
enddo
do m=2*lastN,max,lastN
n(m)=0
enddo
lastN=lastN+1
enddo
!Вывод в файл
do m=2,max,1
if(n(m)/=0) write(1,*) n(m)
enddo
end
Блок-схема
