Przywitanie z zapytaniem o zadanie prime_t (liczby pierwsze)

Witam,

Jest to mój pierwszy post na tym forum więc chciałbym się przywitać :) To po pierwsze :)

Po drugie po wielu latach powracam do korzeni (pascal :D) z czystej chęci przypomnienia sobie o co w tym wszystkim chodziło bez napinania się i bez stresu. Kilka dni temu zarejestrowałem się na spoju ponieważ doszedłem do wniosku że przez rozwiązywanie zadań (prostych) najlepiej przypomnę sobie o co chodzi. No i padło na pierwsze zadanie: liczby pierwsze. Od razu mówię iż przeczytałem regulamin tego forum oraz zapoznałem się z tematami dotyczącymi tego zadania oraz jego rozwiązaniami (dział gotowce itp., np. wątki o rozwiązaniu tego zadania). Generalnie przewija się tam opcja sita ale ponieważ jestem osobą upartą a bardzo ciekawym pomysłem wg. mnie na rozwiązanie tego zadania jest opcja sprawdzenia czy dana liczba dzieli się przez: 2,3,5,7 poszedłem w tą stronę, niestety ciągle otrzymuję złą odpowiedź. Jeśli chodzi o testy z mojej strony to liczby pierwsze do 10 000 wyznacza dobrze (sprawdzone na ideone.com z liczbami pierwszymi od 3 do 10 000 - fakt faktem iż powyżej 10 000 podaje błędną odpowiedź ale zadanie mówi o przedziale do 10 000 choć swoją drogą to ciekawe dlaczego program wysypuje się powyżej tej liczby). Pozwolę sobie zamieścić poniżej kod i jeśli ktoś dla zabicia czasu chciałby go prześledzić i nakierować mnie na błędy w tym kodzie to będę bardzo wdzięczny :) Nie jest to co prawda sprawa honoru ale ciekawi mnie czego jeszcze nie wiem :)

program liczby_pierwsze;
   {$APPTYPE CONSOLE}
var
  licznik,i,j,k,l,x,liczba,lt,ls : longint;
begin
   Readln(lt); //czyla liczbe testow
     for licznik :=1 to lt do
        begin
            ls:=0;
            Readln(liczba); //czyta liczbe

            i:=liczba mod 2;  //dzieli liczbe i zapisuje reszte z dzielenia
            j:=liczba mod 3;  //------||------
            k:=liczba mod 5; //------||------
            l:=liczba mod 7;  //------||------
            x:= i*j*k*l; //jesli jedna ze zmiennych i,j,k,l ma wartosc 0 wtedy wiem ze x=0 wiec liczba nie moze byc pierwsza

            if liczba = 0 then begin writeln('NIE');ls:=1; end;  //na sztywno przypisane wartosci
            if liczba = 1 then begin writeln('NIE');ls:=1; end;
            if liczba = 2 then begin writeln('TAK');ls:=1; end;
            if liczba = 3 then begin writeln('TAK');ls:=1; end;
            if liczba = 5 then begin writeln('TAK');ls:=1; end;
            if liczba = 7 then begin writeln('TAK');ls:=1; end;

                                                                                //zmienna ls sluzy do pomijania wykonywania kolejnego ifa lub jesli ls=0 whtdy sprawdzamy czy x <>0 (jest liczba pierwsza)

            if ls = 0 then
               begin
                 if x=0 then writeln('NIE')
                 else writeln('TAK');
               end;

        end;
end.

Z góry dziękuję za wszelkie rady, sugestie i pomoc :)

dodanie znacznika <code class="delphi"> - furious programming

Witamy na forum. Jeżeli to zadanie nazwane prime_t, to na prywatną wiadomość wysyłam Tobie przykład jak ja je rozwiązałem. Zdaje się, że pomógł mi w tym tutaj @_13th_Dragon jeżeli dobrze pamiętam, bo to było dawno. Ponieważ mój sposób sprawdzania nie wyrabiał się w założonym przez autora czasie. Dlatego nie uzyskiwałem zaliczenia. Ewentualnie może coś więcej Tobie tutaj doradzą pozostali. Przydało by się jednak kod trochę lepiej sformatować, bardziej po ludzku, czyli tradycyjnie 2 spacjowe wielokrotności wcięć i tam gdzie potrzeba. Oraz, co równie ważne, wstawić kod w odpowiedni tag typu delphi lub code=pascal.

powinieneś dodawać i+j+k+l i sprawdzać czy wynik jest >0
mnożąc sprawdzasz czy liczba jest podzielna jednocześnie przez te wszystkie dzielniki

jest opcja sprawdzenia czy dana liczba dzieli się przez: 2,3,5,7

sprawdzać trzeba podzielność przez wszystkie liczby pierwsze w zakresie od 2 do sqrt(x). nie można poprzestawać na 7 :-)

Dziękuję za szybką odpowiedź i za podesłanie kodu :) Jutro na spokojnie go prześledzę. Co do formatowania kodu to masz rację, na razie podzieliłem sobie kod na bloki abym miał lepszy przegląd co jest do czego. Będę starał się pilnować tych wcięć tam gdzie potrzeba :) No i właśnie nie jestem pewien co do tych tagów, mam pisać delphi czy code=pascal?

Pozdrawiam :)

Spoko. Co do tagów to możesz pisać tak albo tak. O ile dobrze kojarzę, to formatowanie nieznacznie się różni kolorami chyba. Ja na ogół wklejam w delphi, bo z Delphi pochodzi większośc kodów jakie tutaj umieszczam. A na PW dostałeś kod z FPC, więc użyłem code=pascal :)

program PRIME_T;
var
  Tablica : array[1..10000] of boolean;
  i, j    : LongInt;
  Liczba  : LongInt;

begin
  Tablica[1] := false;
  for i := 2 to 10000 do
    Tablica[i] := true;

  for i := 2 to 10000 do
    if Tablica[i] then
      for j := 2 to (10000 div i) do
        Tablica[i*j] := false;


  Readln(j);
  for i := 0 to j - 1 do
  begin
    Readln(Liczba);
    if Tablica[Liczba] then Writeln('TAK')
    else Writeln('NIE');
  end;
end.

Babubabu, dziękuję za podesłanie kodu, rzeczywiście wydaje się on być ciekawszą alternatywą niż mój kod :)

_13th_Dragon, dziękuję za rady i nakierowania, olesio pisał mi na PM że sporo mu pomogłeś przy tym zadaniu kilka lat temu no i ja też trochę skorzystałem z Twojej podpowiedzi odnośnie zapętlania tylko do 100. Swoją drogą trzeba wypełnić tablicę true do 10000 ponieważ jeśli wypełnimy ją false to nie będziemy wiedzieć które liczby powyżej 5000 są liczbami pierwszymi (wszędzie będzie false). Faktycznie wystarczy zapętlać do for i := 2 to 100 do aby też otrzymać poprawne wyniki z tym że tak jak już wcześniej pisałem należy zapełnić tablicę wartością true do 10 000.

Na spoju ciekawą rzeczą jest to iż gdy wysłałem kod z pętlą do 100 liczył go w czasie 0.13. Po edycji pętli i zmianie wartości z 100 na 10 000 miałem wynik 0.10. Po kolejnej próbie i zmianie wartości znowu na 100 otrzymałem czas 0.14, po czym znowu zwiększyłem zakres liczenia pętli do 10 000 i otrzymałem czas 0.11. Skąd mogą brać się takie różnice i dlaczego zwiększają się one pomimo tego iż operacji do wykonania jest sto razy mniej?....

P.S.
Jak dodać krótki komentarz pod danym postem nie klikając w dodaj odpowiedź?...

Jurlich napisał(a):

Swoją drogą trzeba wypełnić tablicę true do 10000 ponieważ jeśli wypełnimy ją false to nie będziemy wiedzieć które liczby powyżej 5000 są liczbami pierwszymi (wszędzie będzie false).
Totalne bzdury!

var i,k,v:Integer;
var Tablica:array[1..10000] of Boolean;
const Answer:array[Boolean] of String=('TAK','NIE');
begin
  Tablica[1]:=true;
  for i:=2 to 100 do if not Tablica[i] then for k:=2 to 10000 div i do Tablica[i*k]:=true;
  Readln(k);
  for i:=1 to k do
  begin
    ReadLn(v);
    WriteLn(Answer[Tablica[v]]);
  end;
end.