Sito eratostenesa

0

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.
 
0

Coby się nie powtarzać, przeczytaj moją odpowiedź w tym temacie:
http://4programmers.net/Forum/Newbie/102706-blad_wczytywanie_w_typie_char?p=724631

0

Zmieniłem, ale to niestety nic nie daje - z tego co zauważyłem, to instrukcja read źle działa dla typów znakowych i łańcuchowych, a dla liczbowych dobrze.

0

Wszystko działa dobrze, trzeba tylko wiedzieć jak działa.

popraw
Pierwsze(w, i, b);
Pierwsze(w, n, b);
for wyjściu z pętli wartość zmiennej sterującej jest nieokreślona

oczywiście wiesz, że to nie ma nic wspólnego z Eratostenesem?
starasz się robić wiele rzeczy na raz
zrób jedno a porządnie

0

Sito eratostenesa to odsiewanie liczb złożonych, więc jakiś związek ma.

popraw
Pierwsze(w, i, b);
Pierwsze(w, n, b);
for wyjściu z pętli wartość zmiennej sterującej jest nieokreślona

Nie rozumiem za bardzo co mam tu poprawić, szczególnie, że w programie nie ma takiej instrukcji jak Pierwsze(w, n, b);
Domyślam się, że chodzi ci o końcowy fragment programu, ale nie wiem o co dokładnie.

0

zadanie banalne.. twoje wykonanie do d**y.. za dużo kombinujesz.. każdy program pisze się tak żeby był jak najefektywniejszy.. Twój jest od tego daleki... zamiast tego znajdź najprościej: na necie listę liczb pierwszych z tego przedziału, wrzuć to sobie do stringlisty i w programie daj if'a..

if (sLista.IndexOf(liczba_z_pliku) >= 0) then
TAK
else
NIE

łopatologicznie:

if ((liczba_z_pliku = 3) or (liczba_z_pliku = 5) or (liczba_z_pliku = 7) or (liczba_z_pliku = 11) or ...) then
TAK
else
NIE

albo jakkolwiek inaczej.. array.. predefy.. cokolwiek.. ale nie wyliczaj!

0
zajcev napisał(a)

zadanie banalne.. twoje wykonanie do d**y.. za dużo kombinujesz.. każdy program pisze się tak żeby był jak najefektywniejszy.. Twój jest od tego daleki...

Wystarczy, żeby program działał w założonym czasie, a mój program działa w odpowiednim czasie, tylko zwraca złą odpowiedź.

if (sLista.IndexOf(liczba_z_pliku) >= 0) then
TAK
else
NIE

Wątpię, żeby na tego typu portalach można było korzystać z jakichkolwiek plików, które ja bym miał na kompie.

0

a czy ja mowie o plikach? sciagnij z neta i liste wrzuc w programie dynamicznie.

0

Jakoś mi się nie widzi wklepywać 1229 liczb - równie dobrze mogę dać sobie spokój z tym zadaniem.

1

wkleiłem twój kod i poszło (czas 1.21)
(inaczej zrobiłem to w czasie 0.01)
w sumie pomysł słuszny, szukanie kolejnych liczb pierwszych sprawdzając podzielność przez tylko wcześniej odkryte, ale można by to ładniej napisać (np. czemu służy 2 parametr procedury?), pusta instrukcja po then, albo...
nie chciałeś liczyć zbyt wiele to czemu tablice z zapasem? :)
napisz ładne sito to powiem jak poprawić czas

1 użytkowników online, w tym zalogowanych: 0, gości: 1