Question

Сегодня на уроке информатики рассказывали про то, как получать все простые числа, не превосходящие заданного числа, с помощью метода, который называется решето Эратосфена. Метод заключается в следующем: пусть мы хотим найти все простые числа от 2 до 100. Выпишем числа от 2 до 100, затем возьмем первое число (2), его оставим, а все остальные делящиеся на 2 числа вычеркнем. Затем возьмем первое невычеркнутое число, отличное от 2, это 3. Его оставим, а все остальные еще невычеркнутые и делящиеся на 3 вычеркнем. Затем опять возьмем первое невычеркнутое число, отличное от 2 и 3, это 5, его оставим, а все остальные еще невычеркнутые и делящиеся на 5 вычеркнем. И так далее. В итоге останутся невычеркнутыми только простые числа. Игорю этот метод очень понравился и он решил с его помощью найти все простые числа, не превосходящие 954530. Какое число он вычеркнет последним? Считаем, что каждое число может быть вычеркнуто ровно один раз. То есть, если 30 вычеркнули как делящееся на 2, то вычеркнуть его же как делящееся на 3 мы уже не можем.

Answer 1

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.

Answer 2

Метод решета Эратосфена заключается в последовательном вычеркивании чисел, которые делятся на уже найденные простые числа.

Для нахождения всех простых чисел, не превосходящих 954530, мы начинаем с выписывания всех чисел от 2 до 954530. Затем мы берем первое число (2) и оставляем его, а все остальные числа, делящиеся на 2, вычеркиваем. То есть, мы вычеркиваем все числа, начиная с 4, 6, 8, и так далее.

Затем мы берем первое невычеркнутое число, отличное от 2, это число 3. Мы его оставляем, а все остальные числа, еще невычеркнутые и делящиеся на 3, вычеркиваем. То есть, мы вычеркиваем все числа, начиная с 6, 9, 12, и так далее.

Затем мы берем первое невычеркнутое число, отличное от 2 и 3, это число 5. Мы его оставляем, а все остальные числа, еще невычеркнутые и делящиеся на 5, вычеркиваем. То есть, мы вычеркиваем все числа, начиная с 10, 15, 20, и так далее.

Продолжая этот процесс, мы берем первое невычеркнутое число, отличное от 2, 3 и 5, и так далее. В итоге останутся только невычеркнутые числа, которые и являются простыми числами.

Чтобы найти последнее вычеркнутое число, мы должны продолжать этот процесс до тех пор, пока не останется только одно невычеркнутое число. Это число и будет последним вычеркнутым числом.

Таким образом, чтобы найти последнее вычеркнутое число, мы должны продолжать процесс решета Эратосфена до тех пор, пока не останется только одно невычеркнутое число.