Naiwny test pierwszości - czyli zabawy z rekurencją (część 3)

Liczby pierwsze

Jednym z najprostszych testów pierwszości jest weryfikacja czy dana liczba n posiada dzielnik z przedziału (2, \sqrt{n}) - takie podejście nazywane jest metodą naiwną - i niestety charakteryzuje się dużą złożonością obliczeniową. Nawet przy wykorzystaniu Sita Eratostenesa złożoność obliczeniowa sięga \frac{\sqrt{n}}{\log{n}}. Jednak w cyklu "Zabawy z rekurencją" nie bardzo zwracamy uwagę na złożoność 🙂 , bardziej chodzi o zobrazowanie jak całe algorytmy mogą być łatwo zapisane w postaci krótkich matematycznych funkcji rekurencyjnych - zatem do dzieła 🙂

Rekurencyjne poszukiwanie dzielników

Naszym zadaniem będzie zdefiniowanie funkcji zwracającej 1 jeśli podana liczba n jest liczbą pierwszą oraz 0 w przeciwnym wypadku. Zacznijmy jednak od podania funkcji weryfikującej czy liczba posiada dzielniki.

{\small\text{CzyDzielnik}(n, a, b)=}

{\small=\begin{cases}0&\text{dla}\quad a>b\\1&\text{dla}\quad n \mod a=0\\ \text{CzyDzielnik}(n, a+1, b)&\text{w inn. przyp.}\end{cases}}

Powyższa funkcja zwraca 1 jeśli liczba n posiada dzielnik z przedziału (a,b), oraz 0 w przeciwnym wypadku. Następnie definiujemy wyrażenie reprezentujące naiwny test pierwszości.

{\small\text{CzyPierwsza}(n)=}

{\small=\begin{cases}0&\text{dla}\quad n<2\\ \neg\text{CzyDzielnik}(n,2,\sqrt{n})&\text{dla}\quad n>=2\end{cases}}

Rolą funkcji "CzyPierwsza" jest jedynie "wprawienie algorytmu w ruch" oraz zwrócenie negacji wyniki funkcji "CzyDzielnik". Proste prawda? 🙂 Sprawdźmy więc w mXparser czy to faktycznie działa.

/* Definicja funkcji rekurencyjnych */
Function CzyDzielnik = new Function("CzyDzielnik(n, a, b) = if( a>b, 0, if( n%a = 0, 1, CzyDzielnik(n, a+1, b) ) )");
Function CzyPierwsza = new Function("CzyPierwsza(n) = if( n<2, 0, ~CzyDzielnik(n, 2, sqrt(n)) )", CzyDzielnik);

/* Obliczenie i wyświetlenie wartości */
mXparser.consolePrintln( "CzyPierwsza(1) = " + CzyPierwsza.calculate(1) + ", czas oblicz. = " + CzyPierwsza.getComputingTime() + " s." );
mXparser.consolePrintln( "CzyPierwsza(2) = " + CzyPierwsza.calculate(2) + ", czas oblicz. = " + CzyPierwsza.getComputingTime() + " s." );
mXparser.consolePrintln( "CzyPierwsza(3) = " + CzyPierwsza.calculate(3) + ", czas oblicz. = " + CzyPierwsza.getComputingTime() + " s." );
mXparser.consolePrintln( "CzyPierwsza(4) = " + CzyPierwsza.calculate(4) + ", czas oblicz. = " + CzyPierwsza.getComputingTime() + " s." );
mXparser.consolePrintln( "CzyPierwsza(5) = " + CzyPierwsza.calculate(5) + ", czas oblicz. = " + CzyPierwsza.getComputingTime() + " s." );
mXparser.consolePrintln( "CzyPierwsza(6) = " + CzyPierwsza.calculate(6) + ", czas oblicz. = " + CzyPierwsza.getComputingTime() + " s." );
mXparser.consolePrintln( "CzyPierwsza(7) = " + CzyPierwsza.calculate(7) + ", czas oblicz. = " + CzyPierwsza.getComputingTime() + " s." );
mXparser.consolePrintln( "CzyPierwsza(8) = " + CzyPierwsza.calculate(8) + ", czas oblicz. = " + CzyPierwsza.getComputingTime() + " s." );
mXparser.consolePrintln( "CzyPierwsza(9) = " + CzyPierwsza.calculate(9) + ", czas oblicz. = " + CzyPierwsza.getComputingTime() + " s." );
mXparser.consolePrintln( "CzyPierwsza(10) = " + CzyPierwsza.calculate(10) + ", czas oblicz. = " + CzyPierwsza.getComputingTime() + " s." );

+ wynik

CzyPierwsza(1) = 0.0, czas oblicz. = 0.08 s.
CzyPierwsza(2) = 1.0, czas oblicz. = 0.03 s.
CzyPierwsza(3) = 1.0, czas oblicz. = 0.026 s.
CzyPierwsza(4) = 0.0, czas oblicz. = 0.022 s.
CzyPierwsza(5) = 1.0, czas oblicz. = 0.038 s.
CzyPierwsza(6) = 0.0, czas oblicz. = 0.015 s.
CzyPierwsza(7) = 1.0, czas oblicz. = 0.028 s.
CzyPierwsza(8) = 0.0, czas oblicz. = 0.015 s.
CzyPierwsza(9) = 0.0, czas oblicz. = 0.053 s.
CzyPierwsza(10) = 0.0, czas oblicz. = 0.011 s.

Wygląda na to, że obliczenia są poprawne! Teraz możemy zweryfikować ile jest liczb pierwszych w podanym przedziale, definiując

\pi(n)=\sum_{i=1}^n \text{CzyPierwsza}(i)

/* Definicja wyrażenia sumującego wynik funkcji CzyPierwsza */
Expression pi100 = new Expression("sum(i, 1, 100, CzyPierwsza(i) )");
pi100.addFunctions(CzyPierwsza);

/* Obliczenie i wyświetlenie wyniku */
mXparser.consolePrintln( "Liczba liczb pierwszych w przedziale (1,100) = " + pi100.calculate());

+ wynik

Liczba liczb pierwszych w przedziale (1,100) = 25.0

Pozdrowienia,

Mariusz Gromada

Pamiętajcie, że uruchamiając kody mXparsera należy dodać w nagłówku:

import org.mariuszgromada.math.mxparser.*;

Kod:

 

Zobacz również:

  1. Polowanie na czarownice - czyli zabawy z rekurencją (część 1)
  2. Prędkość ucieczki do nieskończoności - czyli zabawy z rekurencją (część 2)
  3. Rekurencja pośrednia - czyli zabawy z rekurencją (część 4)
Views All Time
Views All Time
428
Views Today
Views Today
1

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *