Sprawdzenie czy liczba jest liczbą pierwszą

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.
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. 
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 :)

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!

0

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

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

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

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