Strona główna » Algorytmy » Artykuły » Silnia liczb Pierwszych
1
 

Silnia liczb Pierwszych

https://mattomatti.com/a0036

Wstęp

Najczęściej w matematyce spotyka się silnię oznaczaną n!. Oznacza ona iloczyn wszystkiech liczb naturalnych mniejszej, równej niż wartość n. Istnieje również wzór ogólny o którym można przeczytać w artykule o silni. W tym artykule przedstawię Silnia dla liczb pierwszych, która pozwala na szybsze szukanie liczb pierwszych w zbiorze liczb naturalnych.

Definicja

Istnieją dwie oddzielne definicji dla tego rodzaju silni. Pierwsze z nich zakłada, że działamy w zbiorze liczb pierwszych, a druga, że naturalnych.

W zbiorze liczb pierwszych

W tym zbiorze funkcja zachowuje się jak tradycyjna silnia dla liczb naturalnych. Wystarczy wyliczyć iloczyn wszystkich liczb pierwszych mniejszy od podanej wartości n. Wtedy n-tą silnię liczb pierwszych opisuje wzór:

Przykładowo p4# = 5·3·2·1 = 30.

W zbiorze liczb naturalnych

W tym zbiorze funkcja jest zapisana w sposób rekurencyjny:

Implementacja

W poniższych implementacjach napiszę funkcję wypiszSilnieLiczbPierwszych(), która zakłada, że znajdujemy się w zbiorze liczb pierwszych, które oczywiście wybieramy ze zbioru liczb naturalnych. Dodatkowo do wyszukiwania liczb pierwszych zostanie wykorzystana poniższa funkcja czyPierwsza():

  1. bool czyPierwsza(int a) {
  2.   for (int i = 2; i <= sqrt(a); i++) {
  3.     if (a % i == 0) {
  4.       return false;
  5.     }
  6.   }
  7.   return true;
  8. }

Rozwiązanie iteracyjne

W celu oszczędzenia zużycia zasobów komputerowych i otrzymać dane w jak najkrótszym czasie zastosujemy iterację. Zasada działania algorytmu polega na tym, że dopóki ma wybierać kolejne liczby pierwsze to szuka kolejnej liczby pierwszej i ją wypisuje.

Zakładamy, że funkcja przyjmuje jeden argument n, która wylicza wartość Silni liczb Pierwszych równą pn#.

  1. int wypiszSilnieLiczbPierwszych(int n) {
  2.   int p = 1;
  3.   int i = 2;
  4.   while (n-- > 0) {
  5.     while (!czyPierwsza(i))
  6.       i++;
  7.     p *= i;
  8.     i++;
  9.   }
  10.   return p;
  11. }

W powyższym przykładzie rozwiązania (2.) zmienna p odpowiada za przechowywanie dotychczasowego iloczynu liczb pierwszych, a (3.) zmienna i pomaga wyszukiwać liczby pierwsze. (4. - 9.) Dopóki nie zostanie pomnożonych n liczb pierwszych to (5. - 6.) są wyszukiwane kolejne liczby pierwsze, (7.) po znalezieniu aktualnej wartości zmiennej p oraz (8.) przejściu do dalszego szukania liczby pierwszej.

Optymalizacja rozwiązania

Zauważmy, że zgodnie z charakterystyką liczb pierwszych jedyna liczb pierwsza, parzysta to 2. Z tego powodu można zoptymalizować działanie kodu poprzez zwiększanie i o 2. Należy jednak pamiętać, żeby wystartować np. z liczby nieparzystej 3. W celu uproszczenia zadania można dodać dwa warunki początkowo, a dalszą część kodu delikatnie zmodyfikować:

  1. int wypiszSilnieLiczbPierwszych(int n) {
  2.   if (n == 0)
  3.     return 1;
  4.   if (n == 1)
  5.     return 2;
  6.   int p = 2;
  7.   int i = 3;
  8.   while (--n > 0) {
  9.     while (!czyPierwsza(i))
  10.       i += 2;
  11.     p *= i;
  12.     i += 2;
  13.   }
  14.   return p;
  15. }

Dodane zostały warunki początkowe (2. - 5.) po których pewne jest, że (6.) p2# = 2, a (7.) dalsze poszukiwania należy zacząć od liczby 3. Dalsza część kodu (8. - 14.) różni się zwiększaniem wartości i o 2.

Testowanie funkcji

W celu wypisania kilku pierwszych wartości pn# wystarczy skorzystać z przygotowanej funkcji main():

  1. int main() {
  2.   for (int i = 0; i < 9; i++) {
  3.     cout << "p" << i << "# = ";
  4.     cout << wypiszSilnieLiczbPierwszych(i) << endl;
  5.   }
  7.   system("pause");
  8.   return 0;
  9. }

Zadania

Zadanie 1

Napisz funkcję, która oblicza n#. Zastosuj rekurencję w celu uproszczenia zapisu. Przetestuj napisaną funkcję.