Sędzia ci go nie przepuszcza ponieważ może w pewnych przypadkach brzegowych dawać nie poprawne wynik lub jest za wolny. Wszystkie sprawdzaczki działają na podobnej zasadzie. Twórca zadania tworzy testy. Każdy z testów składa się z danych wejściowych oraz oczekiwanego wyniku. Każdemu z testów można określić również czas w jakim program rozwiązujący dany problem na podstawie danych zawartym w teście zwraca wynik.
Wysyłając nasz kod, program jest kompilowany, następnie jest uruchamiany dla każdego z przypadków testowych. Sprawdzany jest czas w jakim został obliczony wynik oraz to czy nasz wynik zgadza się z poprawnym wynikiem dla danego testu.
W twoim rozwiązaniu problemem jest zapewne czas tak zwana złożoność obliczeniowa. Wyjaśnijmy sobie następującą kwestię, jeśli chciałbyś stwierdzić czy liczba jest pierwsza czy nie to wystarczy że znajdziesz co najmniej jeden dzielnik większy bądź równy dwa i mniejszy od niej samej. Pierwsze co przyjdzie ci do głowy to takie rozwiązanie:
bool czy_pierwsza(int n)
{
if(n<=1)return false;
for(int i=2;i<n;i++)
{
if(n%i==0)
{
return false;
}
}
return true;
}
Sprawdzam przypadek brzegowy jeśli liczba nie jest 1 to wykonuje pętle for. Jeśli znajdę takie i które jest z przedziału od 2 do n-1 to nastąpi przedwczesne zakończenie pętli. Funkcja zwróci wartość false oznaczająca że podana liczba n nie jest pierwsza. Co jeśli liczba faktycznie jest pierwsza ?
Wtedy pętla for wykona cię n-2 razy. Dla małych liczb pierwszych nie ma to większego znaczenia jednak jeśli na warsztat weźmiemy liczbę 104723. Liczba ta jest liczbą pierwszą, aby to stwierdzić nasz program będzie musiał wykonać aż 104721 operacji. Jak pewnie zauważyłeś nie jest to zbyt optymalne prawda ;)
Naszym celem nie jest sprawdzenie i wyznaczenie wszystkich dzielników, wystarczy że znajdziemy choć jeden. Istnieje takie twierdzenie matematyczne że jeśli liczba ma dzielnik to ten dzielnik jest mniejszy bądź równy pierwiastkowi kwadratowemu z tej liczby.
dzielnik<=sqrt(n)
Pewnie myślisz że wystarczy zamienić i<n na i<=sqrt(n) w warunku końca pętli for. Niestety nie jest to koniec. Komputer wykonuje bardzo dużo obliczeń by obliczyć pierwiastek kwadratowy z dowolnej liczby (Metoda Newtona). Obliczanie pierwiastka jest kosztowne, zysk jaki osiągnęliśmy w ten sposób przez algorytm sqrt został by zmarnotrawiony. Nie martw się wystarczy proste działanie, jakim jest podniesienie tej nierówności stronami do potęgi. Komputery bardzo szybko mnożą.
dzielnik<=sqrt(n) -> dzielnik*dzielnik<=n
Tym sposobem uzyskaliśmy finalny obraz naszej funkcji sprawdzającej czy podana liczba jest pierwsza.
bool czy_pierwsza(int n)
{
if(n<=1)return false;
for(int i=2;i*i<=n;i++)
{
if(n%i==0)
{
return false;
}
}
return true;
}