Напишите программу, которая выводит все простые числа Софи Жермен (такие, что для числа p число 2p + 1 тоже простое) в диапазоне от K до N (2 ≤ K ≤ N ≤ 100000).

Входные данные
Входная строка содержит два натуральных числа, разделённые пробелом, K и N (2 ≤ K ≤ N ≤ 100000).

Выходные данные
Программа должна вывести все простые числа Софи Жермен в диапазоне от K до N в одну строку, разделив их пробелами. Если таких чисел нет, нужно вывести число 0.

Примеры
Входные данные
100 200
Выходные данные
113 131 173 179 191
Входные данные
200 220
Выходные данные
0

Язык: Pascal ABC 1.8

Нужно проверить для каждого числа \(p\) из отрезка от \(K\) до \(N\), что простыми являются и само \(p\), и число \(2p+1\). Удобно заранее найти простые числа решетом Эратосфена до \(2N+1\).

Программа на Pascal ABC:
var
  k, n, i, j, limit: integer;
  prime: array[0..200001] of boolean;
  found: boolean;
begin
  readln(k, n);
  limit := 2 * n + 1;

  for i := 0 to limit do
    prime[i] := true;

  prime[0] := false;
  prime[1] := false;

  i := 2;
  while i * i <= limit do
  begin
    if prime[i] then
    begin
      j := i * i;
      while j <= limit do
      begin
        prime[j] := false;
        j := j + i;
      end;
    end;
    i := i + 1;
  end;

  found := false;
  for i := k to n do
    if prime[i] and prime[2 * i + 1] then
    begin
      write(i, ' ');
      found := true;
    end;

  if not found then
    write(0);
end.

0 0 Пожаловаться