Сегодня на уроке информатики рассказывали про то, как получать все простые числа, не превосходящие заданного числа, с метода, который называется решето эратосфена. метод заключается в следующем: пусть мы хотим найти все простые числа от 2 до 100. выпишем числа от 2 до 100, затем возьмем первое число (2), его оставим, а все остальные делящиеся на 2 числа вычеркнем. затем возьмем первое невычеркнутое число, отличное от 2, это 3. его оставим, а все остальные еще невычеркнутые и делящиеся на 3 вычеркнем. затем опять возьмем первое невычеркнутое число, отличное от 2 и 3, это 5, его оставим, а все остальные еще невычеркнутые и делящиеся на 5 вычеркнем. и так далее. в итоге останутся невычеркнутыми только простые числа. игорю этот метод понравился и он решил с его найти все простые числа, не превосходящие 954530. какое число он вычеркнет последним? считаем, что каждое число может быть вычеркнуто ровно один раз. то есть, если 30 вычеркнули как делящееся на 2, то вычеркнуть его же как делящееся на 3 мы уже не можем.
Ответы на вопрос:
program resheto;
const n=954530;
var i,j,last,k: integer;
b: array[1..n] of boolean;
begin
for j: =1 to n do b[j]: =true; ///сначала все числа не вычеркнуты
b[1]: =false; ///единицу вычеркиваем сразу
i: =2; k: =0; ///k - количество найденных простых чисел
while i*i< =n do
begin
for j: =i+1 to n do
begin
if (b[j]) then ///если число уже вычеркнуто,то ничего не делаем
begin
if (j mod i=0) then begin last: =j; b[j]: =false; end; ///если число делится,то запоминаем его в last и вычеркиваем из решета
end;
end;
inc(i);
end;
for j: =2 to n do if b[j] then inc(k); ///считаем количество
writeln; writeln('последнее вычеркнутое: ',last); writeln('найдено простых чисел: ',k);
for j: =2 to n do if b[j] then write(j,' '); ///выводим все простые числа через пробел
end.
Популярно: Информатика
-
Grotesk107716.04.2021 21:16
-
Киря000131.08.2020 14:01
-
Karolinka2227.09.2020 13:24
-
nkaracheva14.01.2021 10:28
-
vauguq24.10.2022 10:13
-
timurgu0813.12.2022 00:41
-
Barkinhoev06isl26.11.2022 02:59
-
LolKek00620.08.2022 13:41
-
Nastya374822.03.2020 18:40
-
Mariya198515.09.2021 07:48