простые числа (паскаль)

[RAVAL(c)]

Здравствуйте, помогите пожалуйста.
Задача: " найти простые числа в диапазоне м н"
вот мой код:

 
var
 a,b         : array [1..100] of longint;
 i,l,m,n,p,j : longint;
begin
  readln(n,m);
  for i:=2 to m do
    if odd(i)
      then
        begin
          inc(l);
          a[l]:=i;
        end;
  p:=1;
  b[1]:=2;
  for i:=1 to l do
    begin
      if a[i]<>-1
        then
          begin
            inc(p);
            b[p]:=a[i];
            for j:=1 to l do
              if (a[j] mod a[i]=0) and (a[j]<>a[i]) and (a[j]<>-1)
                then a[j]:=-1;
          end;
    end;
  for i:=1 to p do 
    if b[i]>=n
    then writeln(b[i]);
end.

[andrewpalkin]

И в чем проблема кода ? Вроде как все должно работать !

[RAVAL(c)]

не проходит по времени.
если вводить большой диапазон, не успевает обработать за 2секунды

[Tony Parker]

Ваш алгоритм работает за время O(l^2) т.к. самыми долгими являются вложенные циклы по i и j от 1 до l. Это = O([n/2]^2) = O(n^2)

Есть более быстрый алгоритм за O(l*sqrt(n)) = O([n/2]*sqrt(n)) = O(n*sqrt(n)):

var
 a : array [1..100] of longint;
 i,l,m,n,j, q : longint;
begin
  readln(n,m);
  l:= 1;
  a[1]:= 2;
  for i:=2 to m do
    if odd(i) then
    begin
      inc(l);
      a[l]:=i;
    end;
  { проходим по массиву а и заменяем все не простые числа на -1 }
  for i:=1 to l do
  begin
    for j:=1 to i-1 do begin
     q:= sqrt(a[i]);
     if (a[j] > q) break; { т.к. перебираем до sqrt(a[i])}
     if (a[j]<>-1) and (a[i] mod a[j]=0)
       then a[j]:=-1;
    end;
  end;
  for i:=1 to l do 
    if a[i]>=n then writeln(a[i]);
end.

Здесь применена следующая оптимизация:
для того, чтобы число x было простым, достаточно чтобы оно не делилось нацело на все простые числа от 2 до sqrt(x). Т.к. если x - не простое, то оно представимо в виде x = a*b, где a <= b (иначе поменяем а и b местами), откуда a <= sqrt(x). Плюс от 2 до корня перебирать достаточно простые т.к. если число не простое, то оно делится на простое, меньшее его.

[RAVAL(c)]

Tony Parker,твоя программа вообще не ищет простые числа

[Serge_Bliznykov]

думаю, что тут надо применять решето Эратосфена...

кстати, а такое решение "в лоб" не проходит по времени?

function isPrime(X: longint): boolean;
var i: word;
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;
var  
 i,m,n : longint;
begin
   readln(n,m);
   i := n;
   if Not odd(i) then inc(i);
   while i<=m do begin
     if isPrime(i) then Writeln(i); 
     inc(i,2); 
   end; 
end.

[RAVAL(c)]

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

думаю, что тут надо применять решето Эратосфена...

кстати, а такое решение "в лоб" не проходит по времени?

function isPrime(X: longint): boolean;
var i: word;
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;
var  
 i,m,n : longint;
begin
   readln(n,m);
   i := n;
   if Not odd(i) then inc(i);
   while i<=m do begin
     if isPrime(i) then Writeln(i); 
     inc(i,2); 
   end; 
end.

вообще-то моё решение было именно "решетом эратосфена", но видемо из-за вложеного цикла оно не проходит по времени.
вот я и спрашиваю более быструю реализацию алгоритма

[RAVAL(c)]

??????????

[evg_m]

Суть "решета Эратосфена" заключается в отказе от операций деления (в т.ч. и mod), всяческих проверок(кроме границ массива) и использовании быстрого прохода по массиву с заданным приращением индекса.

    j:=i;
    while j<l do begin a[j]:=-1; j:=j+b[p]; end;
//    for j:=1 to l do
//      if (a[j] mod a[i]=0) and (a[j]<>a[i]) and (a[j]<>-1) then 
//        a[j]:=-1;

[Tony Parker]

2 RAVAL(c)

Fixed. Всё ищет. Зацениваем:

var
 a : array [1..100] of longint;
 i,l,m,n,j, q : longint;
begin
  readln(n,m);
  l:= 1;
  a[1]:= 2;
  for i:=2 to m do
    if odd(i) then
    begin
      inc(l);
      a[l]:=i;
    end;
  { проходим по массиву а и заменяем все не простые числа на -1 }
  for i:=1 to l do
  begin
    q:= trunc(sqrt(a[i]));
    for j:=1 to i-1 do if (a[j] > 2) then begin
     if (a[j] > q) then break; { т.к. перебираем до sqrt(a[i])}
     if (a[i] mod a[j]=0)
       then begin
         a[i]:=-1;
         break;
       end;
    end;
  end;
  for i:=1 to l do 
    if a[i]>=n then writeln(a[i]);
end.