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:

• PlayingWithRecursionPart3.java

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)

Poza Liczbami: Inne Twórcze Przestrzenie

Matematyka i muzyka są ściśle powiązane przez rytm, harmonię i struktury

Matematyka i muzyka są ściśle powiązane przez rytm, harmonię i struktury, które wykorzystują matematyczne wzory i proporcje do tworzenia estetycznych i emocjonalnych doznań. Z nieśmiałą ekscytacją przedstawiam moją pierwszą poważniejszą kompozycję, w której starałem się uchwycić te połączenia.

Scalar – zaawansowana aplikacja mobilna z silnikiem matematycznym mojego autorstwa