Liczby pierwsze SPOJ

Question

Witam, mam problem z zadaniem 438 Liczby Pierwsze na SPOJ. Wszystko działa poprawnie kiedy samodzielnie sprawdzam liczby ale sędzia nie uznaje kodu (błędna odpowiedź). Proszę o pomoc. Link z kodem: https://pastebin.com/aeb8E6fD

Comments

Możesz dać link do treści zadania? algorytm sprawdzający może nie uznać odpowiedzi bo jest gdzieś literówka...

---

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, w przeciwnym wypadku.

---

Input:
3
11
1
4

Output:
TAK
NIE
NIE

Answer 1

2 jest liczbą pierwszą, na pewno to masz błędne, co dalej nie wiem.

Answer 2

Ty testowałeś w ogóle ten swój kod, zanim wysłałeś go na SPOJa? Przecież on zwraca jakieś bezsensowne odpowiedzi - liczba 4 jest rzekomo pierwsza, a 11 już nie.

Jak mój poprzednik słusznie zauważył, 2 jest liczbą pierwszą, więc ten if jest niepoprawny.

if(n==2)
    cout<<"NIE"<<endl;

Znasz definicję liczby pierwszej? Liczba pierwsza to taka, która dzieli się tylko przez 1 i przez samą siebie.

Ty natomiast w poniższej instrukcji warunkowej uznajesz, że liczba nie jest pierwsza, na podstawie tego, że nie dzieli się ona przez kolejne liczby naturalne. A liczba pierwsza ma być właśnie niepodzielna przez kolejne liczby naturalne (za wyjątkiem tych dwóch, o których wspomniałem wcześniej).

Najprostszym sposobem na sprawdzenie, czy liczba jest pierwsza, jest pętla:

for (unsigned i = 2; i <= sqrt(value); ++i) {
    //...
}

Rozpoczynamy sprawdzanie podzielności od liczby dwa, a kończymy na pierwiastku z liczby (jest to optymalizacja, jeżeli liczba nie jest podzielna przez wartości mniejsze od pierwiastka, to na pewno nie będzie też podzielna przez te większe - warto pomyśleć nad tym chwilę). W ten sposób pomijamy sprawdzanie podzielności przez 1 i przez samą siebie, bo to akurat podzielności oczywiste.