Strona główna » Algorytmy » Artykuły » Bezpieczne Liczby Pierwsze
 

Bezpieczne Liczby Pierwsze

https://mattomatti.com/a0200

Definicja

Bezpieczne Liczby Pierwsze to takie liczby pierwsze, które są postaci 2p + 1, gdzie liczba p też jest liczbą pierwszą. Wszystkie takie liczby są liczbami nieparzystymi.

Przykład

Najmniejszą Bezpieczną Liczbą Pierwszą jest 5, ponieważ zarówno 5 i 2 są liczbami pierwszymi. Innym przykładem jest liczba 23, ponieważ zarówno 11 jak i 23 są liczbami pierwszymi.

Ciąg Liczb

Liczby można ustawić w następujący ciąg: 5, 7, 11, 23, 47, 59, 83, 107, 167, 179, 227, ..

Implementacja

Czy Bezpieczna?

Do sprawdzania czy dana liczba jest Bezpieczną Liczbą Pierwszą wystarczy dowolny algorytm, który określi czy dana liczba jest liczbą pierwszą. Przykłady rozwiązań tego zagadnienia można znaleźć w artykule o Liczbach Pierwszych. Mając funkcję czyPierwsza() można bardzo łatwo napisać funkcję, która sprawdzi żądaną wartość:

  1. bool czyBezpiecznaLiczbaPierwsza(int a) {
  2.   int p = (a - 1) / 2;
  3.   return czyPierwsza(a) && czyPierwsza(p);
  4. }

Funkcja składa się z obliczenia wartości p, a wynik końcowy jest prawdziwy tylko, gdy a i p są pierwsze. Wykorzystanie takiej metody jest bardzo efektywne dla pojedynczej wartości, ponieważ złożoność wynosi O(sqrt(a)). Nie jest to jednak najskuteczniejsza metoda, gdy chcemy wygenerować listę Bezpiecznych Liczb Pierwszych.

Lista Liczb

W celu wygenerowania listy liczb można by sprawdzić czy p jest pierwsze, a następnie sprawdzić czy n = 2p + 1 też jest. Warto jednak zauważyć, że lepiej jest zacząć szukać liczb pierwszych od końca, a następnie zaznaczyć w tabeli, które są liczbami pierwszymi. Uzupełniając w ten sposób chcąc sprawdzić czy n jest pierwsze wystarczy tylko pobrać taką informację z tabeli. Oznacza to dwukrotnie mniej operacji sprawdzania do wykonania niż, gdyby generować listę liczb przy pomocy poprzedniego algorytmu.

Poniżej została zamieszczona funkcja realizująca ten kod. Należy pamiętać, że choć obliczenia zostają wykonane szybciej to obciąża ona pamięć. Złożoność pamięciowa wynosi O(n).

  1. void wypiszBezpieczneLiczbyPierwsze(int n) {
  2.   if (n % 2 == 0)
  3.     n -= 1;
  4.   bool * tab = new bool[n + 1];
  5.   for (int i = 2 * n + 1; i > 0; i -= 2) {
  6.     tab[i / 2] = czyPierwsza(i);
  7.     if (2 * i + 1 <= n && tab[i / 2] && tab[i]) {
  8.       cout << 2 * i + 1 << " ";
  9.     }
  10.   }
  11.   if (n >= 5)
  12.     cout << 5;
  13. }

Na początku upewniamy się, że liczba n jest nieparzysta (jedyną liczbą pierwszą jest 2), a następnie tworzymy tablicę pomocniczą. W pętli zaczynając od 2n + 1 przechodzimy po kolejnych liczbach nieparzystych, a kolejne wyniki zapisujemy na kolejnych pozycjach. Kiedy i będzie z zakresu [1, n] to sprawdzamy czy aktualna wartość oraz ta dwa razy większa są liczbami pierwszymi. Jeśli tak to wypisujemy liczbą. Na koniec należy pamiętać, że 5 powstaje poprzez sprawdzenie liczby 2 co w pętli nigdy nie nastąpi, więc należy wypisać tę liczbą oddzielnie.

Testowanie funkcji

Do przetestowania kodu można wykorzystać następującą fragment:

  1. int main () {
  2.   int a;
  3.   cout << "Podaj liczbe do sprawdzenia\n a = ";
  4.   cin >> a;
  5.   bool wynik = czyBezpiecznaLiczbaPierwsza(a);
  6.   cout << (wynik ? "Tak" : "Nie");
  7.   system("pause");
  8.   return 0;
  9. }