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(&quot;CzyDzielnik(n, a, b) = if( a&amp;amp;gt;b, 0, if( n%a = 0, 1, CzyDzielnik(n, a+1, b) ) )&quot;);
Function CzyPierwsza = new Function(&quot;CzyPierwsza(n) = if( n&amp;amp;lt;2, 0, ~CzyDzielnik(n, 2, sqrt(n)) )&quot;, CzyDzielnik);

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

+ 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(&quot;sum(i, 1, 100, CzyPierwsza(i) )&quot;);
pi100.addFunctions(CzyPierwsza);

/* Obliczenie i wyświetlenie wyniku */
mXparser.consolePrintln( &quot;Liczba liczb pierwszych w przedziale (1,100) = &quot; + 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)

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.

I Am Here – RELEARN – Mariusz Gromada (2024)
I Am Here – RELEARN – Mariusz Gromada (2024)
Deep Under – RELEARN – Mariusz Gromada (2024)
Deep Under – RELEARN – Mariusz Gromada (2024)

Scalar – zaawansowana aplikacja mobilna z silnikiem matematycznym mojego autorstwa

Views All Time
Views All Time
3253
Views Today
Views Today
2

Dodaj komentarz

Twój adres e-mail nie zostanie opublikowany. Wymagane pola są oznaczone *