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&gt;b, 0, if( n%a = 0, 1, CzyDzielnik(n, a+1, b) ) )"); Function CzyPierwsza = new Function("CzyPierwsza(n) = if( n&lt;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.0Pozdrowienia,
Mariusz Gromada
Pamiętajcie, że uruchamiając kody mXparsera należy dodać w nagłówku:
import org.mariuszgromada.math.mxparser.*;Kod:
Zobacz również:
- Polowanie na czarownice – czyli zabawy z rekurencją (część 1)
- Prędkość ucieczki do nieskończoności – czyli zabawy z rekurencją (część 2)
- Rekurencja pośrednia – czyli zabawy z rekurencją (część 4)
