Sprawdzenie czy liczba jest liczbą pierwszą

2011-09-29 12:38
0

Witam, w ramach ćwiczeń robie sobie zadanka ze SPOJ.
Robię sobie zadanie sprawdzające czy dana liczba jest liczbą pierwszą. Kod który napisałem wydaje się poprawny jak go sprawdzam na kompie, ale gdy wysyłam do sprawdzenia to pokazuje mi błąd. Czy ktoś mógłby mi go wskazać?

Treść zadania

Sprawdź, które spośród danych liczb są liczbami pierwszymi
Input
n - liczba testów n<100000, w kolejnych liniach n liczb z przedziału [1..10000]

Output
Dla każdej liczby słowo TAK, jeśli liczba ta jest pierwsza, słowo: NIE, jeśli jest złożona.

Example
Input:
3
11
1
4
Output:
TAK
NIE
NIE

KOD:

program PRIME_T;
var
a: array [1..100000] of integer;
n:integer;
i,b,c,j:integer;

begin
b:=0;
readln(n);
for i:=1 to n do readln(a[i]);
  for i:=1 to n do
  begin
    c:=0;
    for j:=1 to a[i] do
    begin
      b:=a[i] mod j;
      if (b=0) then c:=c+1;
    end;
    if (c=2) then writeln('TAK') else writeln('NIE');
  end;
end.

Pozostało 580 znaków

2011-09-29 13:19
0

Nie zauważyłeś, że tym błędem jest przekroczenie limitu czasu?
Twój program działa dramatycznie zbyt wolno.
Czy for musi kręcić się od 1 do a[i]?
a jeżeli już znalazłeś jakiś dzielnik (poza 1) to warto sprawdzać dalej?

A tak nie było by ładniej?

program PRIME_T;

function Czy(n:integer):boolean;
begin
tu coś pomyśl
end;

var
    n,a:integer;
begin
    readln(n);
    while n>0 do begin
        readln(a);
        if czy(a) then
            writeln('TAK')
        else
            writeln('NIE');
        dec(n);
    end
end. 

Pozostało 580 znaków

2011-09-29 20:51
0

um, no wydawało mi się że tak bo jak ktoś poda większą liczbę która nie jest liczbą pierwszą (np 10000) to jeśli zatrzymam sprawdzanie po znalezieniu 2 (1 i jakiś jeszcze) dzielników to będzie błąd? Ale dzięki za odpowiedź, myślałem że jeśli program u mnie w kilka sec rozwiązuje problem to w miarę szybko jest :)

Pozostało 580 znaków

2011-09-30 13:22
0

trick w tym zadaniu polega na tym, żeby wszystko policzyć zanim program wystartuje. Ile jest liczb pierwszych w przedziale 1 do 10000? Tylko 1230!


Jeśli chcesz pomocy, NIE pisz na priva, ale zadaj dobre pytanie na forum.
dokładnie 1229 - Xitami 2011-09-30 17:21

Pozostało 580 znaków

2011-09-30 15:36
0

Odpowiedzią na to zadanie jest sito Erastotelesa - jak zrobisz zgodnie z algorytmem z wikipedii to na 100% przejdzie.

Pozostało 580 znaków

2011-09-30 15:45
0

W sumie to można na 3 sposoby:

  1. Lecisz po wszystkich liczbach i patrzysz czy są pierwsze. Musisz to zrobić jak najszybciej, więc trzeba użyć testu Millera-Rabina, albo czegoś takiego.
  2. Sito Erastotenesa.
  3. Preprocessing, generujesz sobie liczby pierwsze od 1-10000 jakimś programem, nawet najwolniejszym, potem zapisujesz do pliku, wklejasz do tablicy i potem tylko patrzysz czy liczba na wejściu jest w tablicy(można to zrobić w czasie O(log n), więc bardzo szybko).

Pozostało 580 znaków

2011-09-30 15:52
0
  1. Preprocessing, generujesz sobie liczby pierwsze od 1-10000 jakimś programem, nawet najwolniejszym, potem zapisujesz do pliku, wklejasz do tablicy i potem tylko patrzysz czy liczba na wejściu jest w tablicy(można to zrobić w czasie O(log n), więc bardzo szybko).

Najlepiej zapisać wyniki w postaci flag binarnych i sklastrować do wartości szesnastkowych.

Co do czasu dostępu, to zakładając, że numer liczby pierwszej jest w dużej mierze proporcjonalny do liczba/ lg liczba, to wybór jednego elementu można by skrócić do średniego czasu stałego poprzez proste oszacowanie indeksu najbliższej liczby pierwszej.

Edit:
Oczywiście uwaga 1. dotyczy sytuacji w której mamy mapę bitową, a uwaga 2. dotyczy sytuacji, w której mamy posortowaną listę liczb pierwszych z danego zakresu. W przypadku małego zakresu mapa bitowa powinna być oszczędniejsza pamięciowo, a zarazem przy jej użyciu mamy gwarantowany czas dostępu O(1), więc dla małych zakresów to jest najsensowniejsza opcja.


"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.
edytowany 1x, ostatnio: Wibowit, 2011-09-30 15:58
tylko czy na pewno jest to 'najsensowniejsza' opcja, biorąc pod uwagę, że jest to zadanie ze SPOJa oznaczone jako łatwe i bez, no powiedzmy skomplikowanych struktur danych, możliwe jest napisanie rozwiązania na 100 pkt? Nawet nie wiem, czy tu wystarczająca nie będzie złożoność O(n*sqrt a) - dla wszystkich liczb lecimy od 2 do pierwiastka i patrzymy czy znajdziemy dzielnik, oczywiście przerywając jeśli takowy znajdziemy. Jest to chyba rozwiązanie najprostsze i bardziej dostosowane do poziomu zadania. - piternet 2011-09-30 16:07

Pozostało 580 znaków

2011-09-30 17:34
0

Jeżeli mówimy o testowaniu "pierwszości" to po pierwsze pytamy o zakres.
Tu mamy max 10000 czyli wystarczająco dobra jest dowolna metoda, byle zrealizowana sensownie.
A okaże się, że większość czasu zajmuje I/O
Można np.tak: http://ideone.com/jvcLQ

edytowany 1x, ostatnio: Xitami, 2011-09-30 17:36

Pozostało 580 znaków

Liczba odpowiedzi na stronę

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