Strona główna » Algorytmy » Artykuły » Liczby Uparte
 

Liczby Uparte

Definicja

Liczby Uparte to takie liczby nieparzyste, których nie można wyrazić przy pomocy pewnej potęgi liczby 2 oraz liczby pierwszej. Oznacza to, że liczba Uparta jest postaci 2i + p, gdzie i ≥ 0.

Przykład

Najmniejszą liczbą upartą jest 1, ponieważ 20 = 1, a wtedy p = 0, ale 0 nie jest liczbą pierwszą. Drugą liczbą upartą jest 127. Można to udowodnić sprawdzając wszystkie potencjalne rozkłady:

i2ipKomentarz01126p nie jest pierwsze, dzielnik 212125p nie jest pierwsze, dzielnik 524123p nie jest pierwsze, dzielnik 338119p nie jest pierwsze, dzilenik 7416111p nie jest pierwsze, dzilenik 353295p nie jest pierwsze, dzielnik 566463p nie jest pierwsze, dzielnik 3

Jak wynika z tabelki niezależnie od wybranej pary warunek rozkładu nigdy nie został spełniony.

Ciąg liczb

Ustawiając liczby w ciąg otrzymujemy: 1, 127, 149, 251, 331, 337, 373, 509, 599, 701, ...

Implementacja

W celu zaimplementowania funkcji do sprawdzania czy dana liczba jest Uparta należy dodać funkcję do sprawdzania czy liczba jest pierwsza. W ten sposób możliwe jest sprawdzenie czy rozpatrywany rozkład jest prawidłowy. Więcej informacji o sprawdzaniu czy liczba jest pierwsza można znaleźć tutaj.

  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. }

Teraz można przejść do pisania funkcji czyUparta(), która dla danego argumentu a zwróci wartość logiczną czy tak jest. Oto przykładowy kod funkcji:

  1. bool czyUparta(int a) {
  2.   if (a % 2 == 0)
  3.     return false;
  4.   int i = 1;
  5.   while (i < a) {
  6.     if (czyPierwsza(a - i))
  7.       return false;
  8.     i *= 2;
  9.   }
  10.   return true;
  11. }

Sprawdzanie polega na wyliczaniu kolejnych potęg liczby dwa i sprawdzaniu czy różnica pomiędzy daną potęgą oraz sprawdzaną liczba jest liczbą pierwszą. Jeśli tak jest to należy zwrócić fałsz. Jeśli jednak pętla nie zostanie przerwana to liczba na pewno jest Upartai należy zwrócić prawdę.

Testowanie funkcji

Poniższy kod pozwala na wczytanie liczby od użytkownika, a następnie wypisanie czy przekazana liczba jest liczba Upartą.

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