Sprawdzanie czy zadana liczba jest liczbą pierwszą
Zacznijmy od zdefiniowania czym są liczby pierwsze. Liczby pierwsze to te liczby naturalne większe od 1, które mają tylko dwa dzielniki naturalne - jedynkę i samą siebie.
Liczby pierwsze mają bardzo duże znaczenie w informatyce, bowiem wyznaczanie dużych liczb pierwszych wymaga bardzo dużej mocy obliczeniowej komputera. Dlatego też w wielu algorytmach szyfrowania danych stosuje się jako ważny element bezpieczeństwa właśnie liczby pierwsze.
Sprecyzujmy warunki algorytmu:
Dane: liczba n - liczba naturalna
Wynik: określenie, czy zadana liczba n jest liczbą pierwszą czy liczbą pierwszą nie jest.
Algorytm w postaci listy kroków (wersja naiwna)
-
Dla zmiennej pomocniczej i od 2 do n-1 wykonaj:
- Jeśli reszta z dzielenia n przez i jest równa 0, to zakończ krok 1 i przejdź do kroku 2
- Jeśli i wynosi n, to liczba n jest liczbą pierwszą, w przeciwnym wypadku liczba n jest liczbą złożoną.
Przedstawiony powyżej algorytm to tzw. algorytm naiwny, czyli najprostszy sposób rozwiązania problemu i jednocześnie bardzo wolny.
Sam algorytm polega na tym, że dla zadanej liczby n sprawdzamy po kolei, czy liczba n jest podzielna przez kolejne liczby naturalne zaczynając od 2. Jeśli liczba n jest podzielna przez którąś z liczb, to nie musimy dokonywać dalszego sprawdzania, bowiem wiemy już, że liczba n nie jest liczbą pierwszą.
Do ostatecznego stwierdzenia, czy liczba n jest liczbą pierwszą, sprawdzamy wartość zmiennej pomocniczej. Jeśli wartość zmiennej pomocniczej jest równa wartości liczby n, to znaczy, że liczba n nie dzieliła się przez żadną z liczb, czyli jest liczbą pierwszą. Z kolei, jeśli wartość zmiennej pomocniczej jest mniejsza od n, to znaczy, że liczba n była podzielna przez którąś z liczb, czyli, że liczba n nie jest liczbą pierwszą
Sam algorytm jest prawie najprostszą wersją algorytmu, bowiem w najgorszym wypadku będziemy musieli sprawdzić wszystkie liczby mniejsze od n, aby się przekonać, że liczba n jest rzeczywiście liczbą pierwszą.
Z drugiej jednak strony, w kroku 1, o ile liczba n podzieli się przez bieżącą wartość zmiennej pomocniczej, to przechodzimy do kroku 2, dzięki czemu zyskujemy nieco na szybkości działania algorytmu.
Zwróć uwagę, że zmienna i przebiega wartości od 2 do n-1 włącznie. Nie sprawdzamy natomiast podzielności liczby n przez 1 i przez samą siebie, bowiem każda liczba (zarówno pierwsza, jak i złożona) dzieli się przez jedynkę i samą siebie, więc takie sprawdzenie by nam zupełnie nic nie dało.
