Testy pierwszości w języku PHP...

Witam Was wszystkich. Dzisiaj opiszę jak sprawdzić czy dana liczba jest liczbą pierwszą. Funkcja będzie napisana w języku PHP.

Aby sprawdzić, czy liczba naturalna n jest liczbą pierwszą, należy dzielić ją kolejno przez wszystkie liczby większe od 1 i mniejsze równe od floor(n/2). Jeśli przy każdym dzieleniu reszta z dzielenia jest różna od zera, to dana liczba n jest liczbą pierwszą. Natomiast jeżeli choć jedno dzielenie daje resztę równą zero, to sprawdzana liczba naturalna jest liczbą złożoną.

Oto przykład funkcji sprawdzającej czy dana liczba n jest liczbą pierwszą. Funkcja została napisana w języku PHP

function is_prime($n)
{
$wynik=0;
$i=2;
$g=floor($n/2);
while (($wynik==0) & ($i<=$g))
{
if ($n%$i==0) ++$wynik;
++$i;
}
if ($wynik==0) return(0);
else return(1);
}

Funkcja nazywa się is_prime i ma jeden argument - liczbę n, na której musimy wykonać test pierwszości. Najpierw tworzymy pętle w której dzielimy liczbę n przez kolejne liczby naturalne począwszy od liczy 2 aż do floor(n/2). Jeżeli w którymś momencie liczba n będzie podzielna przez daną liczbę i to opuszczamy pętlę i funkcja zwraca wynik 1 - czyli liczba n jest liczbą złożoną. W przeciwnym wypadku funkcja zwraca wynik 0 - czyli liczna n jest liczbą pierwszą.

Powyższy test jest bardzo dokładny, ale niestety ma dużą złożoność obliczeniową. Można również stworzyć probabilistyczny test pierwszości, który jest bardzo szybki. Jednak istnieje niewielkie prawdopodobieństwo pomyłki. Oto algorytm:

 

Algorytmy probabilistyczne z bardzo dużym prawdopodobieństwem sprawdzają czy dana liczba jest liczbą pierwszą. Ale niestety istnieje niewielki prawdopodobieństwo pomyłki. W powyższym algorytmie prawdopodobieństwo pomyłki jest mniejsze niż 1/200 procent.

Jeżeli chcesz sprawdzić czy dana liczbą pierwszą to zapraszam do poniższej aplikacji:

 

Test pierwszości