Witam!
Mam problem z prostym zadaniem ze spoja: http://pl.spoj.pl/problems/PRIME_T/
Napisałem kod, ale nie wiem dlaczego mam błędną odpowiedź (nie mogę znaleźć liczb dla których odpowiedź jest błędna). Zadanie łatwe, więc mam nadzieję, że ktoś wskaże mi błąd.
W moim programie wybieram najpierw największy z wprowadzonych elementów, i sprawdzam, czy liczby <= od tego elementu są pierwsze. Jeżeli są to w tablicy b zapisuję 1, w przeciwnym razie 0 (przykładowo sprawdzam 25, nie jest pierwszą więc b[25]:=0). Dalej już tylko sprawdzam tablicę a po kolei i jeżeli b[a[i]] = 0 to wypisuję tak, w przeciwnym wypadku nie. Tyle, że są dane dla których algorytm nie działa.
Oto kod:
Program Sito;
type
tablica1 = array[1..100000] of integer;
tablica2 = array[1..10000] of byte;
var
i, w : integer; { w - max }
a : tablica1;
n : longint;
b : tablica2;
Procedure Pierwsze(w, i : integer; var b : tablica2);
var
c : array[1..2000] of integer; { lokalna tablica liczb pierwszych }
k, j : integer;
begin
b[1] := 0;
b[2] := 1;
b[3] := 1;
c[1] := 3;
b[4] := 0;
b[5] := 1;
b[6] := 0;
c[2] := 5;
k := 2;
i := 7;
while i <= w do
begin
b[i] := 1;
for j := 1 to k do
begin
if i mod c[j] <> 0 then
else begin b[i] := 0; break end
end;
if b[i] = 1 then begin c[k+1] := i; k := k + 1 end;
b[i+1] := 0;
i := i + 2
end
end;
begin
readln(n);
w := 0;
for i := 1 to n do
begin
readln(a[i]);
if a[i] > w then w := a[i]
end;
Pierwsze(w, i, b);
for i := 1 to n do
begin
if b[a[i]] = 1 then
writeln('TAK') else writeln('NIE')
end
end.