Strona główna » Algorytmy » Teoria Liczb » Liczby Fortunatego
 

Liczby Fortunatego

https://mattomatti.com/a0013

Definicja

Liczby Fortunatego to taka liczba naturalna m > 1 dla danej wartości n dla której p(n) + m jest liczbą pierwszą. Funkcja p(k) to iloczyn k początkowych liczb ciągu liczb pierwszych.

Ciąg, przykłady

Liczby Fortunatego można ustawić w ciąg: 3, 5, 7, 13, 23, 17, 19, 23, 37, 61, ..

Pierwszą liczbą Fortunatego jest 3, ponieważ p(2) = 2. Dla m = 2 liczba 4 nie jest piersza, ale właśnie dla m = 3 liczba 5 jest pierwsza. Bardziej złożonym przykładem jest czwarta liczba: 13. Wtedy p(4) = 2·3·5·7 = 210. Najmniejsza liczba m wynosi wtedy 23, ponieważ 233 jest liczbą pierwszą.

Ciekawostka

Istnieje przypuszczenie, że wszystkie liczby Fortunatego są liczbami pierwszymi. Nie znaleziono do tej pory żadnej liczby złożonej będącej liczbą Fortunatego.

Implementacja

Napisany poniżej program ma za zadanie wypisać na ekran ciąg liczb Fortunatego.

Liczba pierwsza

W trakcie pisania funkcji zaistnieje potrzeba sprawdzenia czy liczba jest pierwsza. Wyjaśnienie kodu można znaleźć w artykule o liczbach pierwszych.

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

Pobierz liczbę Fortunatego

Zadanie polegające na szukaniu kolejnych liczb Fortunatego można rozbić na dwa etapy: szukanie iloczynu n początkowych liczb pierwszych, a potem wyszukiwanie wartości m. Funkcja getFortunate() przyjmuje jeden argument n, który określa, którą z kolei liczbę Fortunatego program ma wyliczyć.

  1. int getFortunate(int n) {
  2.   int p = 1;
  3.   for (int i = 0, j = 2; i <= n; i++) {
  4.     while (!czyPierwsza(j)) {
  5.       j++;
  6.     }
  7.     p *= j;
  8.     j++;
  9.   }

(2.) Zainicjalizuj zmienną p, która będzie przechowywać iloczyn liczb pierwszych. (3.) W pętli znajdź n liczb pierwszych poprzez (4. - 6.) wyszukanie następnej liczby, (7.) wyliczenie iloczynu i (8.) przejście do poszukiwań następnej liczby pierwszej.

  1.   int m = 2;
  2.   while (!czyPierwsza(p + m)) {
  3.     m++;
  4.   }
  5.   return m;
  6. }

Z kolei w drugim etapie (10.) przyjmij za m najmniejszą prawidłową liczbę czyli 2. Następnie (11.) w pętli dopóki suma iloczynu oraz m nie jest pierwsza to (12.) zwiększaj m. (14.) Na koniec zwróć znalezioną wartość m.

Testowanie funkcji

W celu przetestowania działania napisanej funkcji można skorzystać z poniższej funkcji main(), która wypisuje na ekran pierwsze pięć liczb Fortunatego:

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

Zadania

Zadanie 1

Napisz funkcję int listFortunate(int k), która będzie przyjmowała argument całkowitoliczbowy k i dla podanej liczby wypisze na ekran pierwsze k liczb Fortunatego posortowane rosnąco i bez powtórzeń.