Задача по Pascal

[NikitosNP]

Добрый вечер)Помогите пожалуйста)
В интервале от а до b найти все парные простые числа. Парными простыми числами называют два простых числа, разность между которыми равна 2. Например, 3 и 5, 11 и 13, 17 и 19.

Желательно с комментариями к задаче
Спасибо)

[Poma][a]

Так-с.. Такие числа называются простыми числами близнецами (если я не ошибаюсь), так что гуглите. Недавно решал её (код в школе ) и помнится я делал тупым перебором (только четные числа отбрасывал..) и скорость была удовлетворительная..
Набросок моего решения :

i := a + Ord(Odd(a));
b := b - Ord(Not(Odd(b)));

while i+2 <= b do begin
       if IsPrime(i) and (IsPrime(i+2)) then
            WriteLn (i, ' ', i+2);
       Inc (i, 2)
end;

Не проверял

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

Вариант#1
Просто берем и загоняем в массив простые числа из промежутка [A, B] (для скорости возьмем решето Эратосфена или решето Аткина)
Теперь бежим по массиву и если a[i+1] - a[i] = 2, то выводим

Вариант#2
Этот вариант является просто маленькой оптимизацией вариант#0

f1 := IsPrime(i);
while ... begin
    f2 := Is Prime(i+2);
    if f1 and f2 then
       WriteLn (..);
    f1 := f2
end;

[Stilet]

IsPrime(i)

Рома, а может тогда стоит еще и ссылку на эту функцию кинуть, раз уж воспользовался ею?

[Serge_Bliznykov]

на форуме по данному слову легко найди данную функцию.
но, раз такой вопрос возник, почему бы сюда и выложить код, будет 900000 + 1 тема с данным кодом!

{вычисление простых чисел в диапазоне a..b}

function isPrime(X: LongInt): boolean;
var i: integer;
Begin
     isPrime:=false;
     if x<2 then Exit;
     if not odd(x) and (x<>2) { проверяем на чётность  }
          then exit;
     i:=3;
     while i <= sqrt(x) do { проверяем только нечётные }
     begin
          if x mod i = 0 then Exit;
          inc(i,2);
     end;
     isPrime:=true;
End;

[s-andriano]

Сообщение от Serge_Bliznykov

на форуме по данному слову легко найди данную функцию.
но, раз такой вопрос возник, почему бы сюда и выложить код, будет 900000 + 1 тема с данным кодом!

В данном конкретном случае это неправильная функция.
Правильная должна примерно выглядеть так:

function IsPrime(n : longint) : boolean;
begin
  result := PrArray[n div 2];
end;

Где PrArray - заранее подготовленный при помощи "решета Эратосфена" массив.

[Serge_Bliznykov]

Сообщение от s-andriano

В данном конкретном случае это неправильная функция.
Правильная должна примерно выглядеть так:

Да ладно, "неправильная" - это правильная функция проверки числа на простоту!

BTW, а Вы только мой пост прочитали? Или удосужились выше сообщение посмотреть, где Poma][a использовал данную функцию?


p.s. и откуда взялось n div 2 ?!

[Poma][a]

Моя функция, проигрывающая варианту Сержа

function IsPrime (n : Integer): Boolean;
var
   i, sq : Integer;
   
begin
     IsPrime := FALSE;
     sq := Trunc (Sqrt(n)); // решил не заморачиваться 
     
     for i := 2 to sq do
         if n mod i = 0 then
            Exit;
            
     IsPrime := TRUE
            
end;

p.s. и откуда взялось n div 2 ?!

Мы ведь отбрасываем четные варианты, а их - половина.


Мой полный код (написан он тупо (= без какой-либо оптимизации)) :

const
     SIZE = 1000;
     
function IsPrime (n : Integer): Boolean;
var
   i, sq : Integer;
   
begin
     IsPrime := FALSE;
     sq := Trunc (Sqrt(n));
     
     for i := 2 to sq do
         if n mod i = 0 then
            Exit;
            
     IsPrime := TRUE
            
end;
     
var
   i : Integer;
   
begin
     i := 3;
     
     while i <= SIZE do begin
           if IsPrime(i) and IsPrime(i+2) then
              WriteLn (i, ' ', i+2);
           Inc (i, 2)
     end
     
end.