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

Liczby Goldbacha

https://mattomatti.com/a87

Definicja

Liczby Goldbacha jest to taka liczba naturalna, którą można zapisać przy pomocy dwóch liczb pierwszych.

Hipoteza

Liczby Goldbacha mają związek z Hipotezą Goldbacha, która mówi, że każdą liczbę parzystą większą od 2 może zostać przedstawiona jako suma dwóch liczb pierwszych. Podczas formułowania hipoteza brzmiała inaczej, ponieważ jeszcze w XVIII wieku zaliczono 1 do liczb pierwszych.

Przykład

Weźmy przykładowo liczbę 58. Można ją przedstawić jako sumę dwóch liczb pierwszych: 5 i 53. Choć Hipoteza dotyczy liczb parzystych to większość liczb nieparzystych również można zapisać w ten sam sposób. Przykładem takiego rozkładu może być liczba 73, która jest sumą 2 i 71.

Ogólnie liczby Goldbacha można ustawić w ciąg, którego początkowe wyrazy to: 4, 5, 6, 7, 8, 9, 10, 12, 13, 14, ...

Implementacja

Liczby pierwsze

Liczb Goldbacha nie można szukać bez znajomości liczb pierwszych. Przydatna okaże się 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. }

Czy Goldbach

Sprawdzenie czy podana liczba a jest liczbą Goldbacha można sprawdzić poprzez szukanie jej rozkładu. Wystarczy rozpocząć od pary (2, a - 2), a następnie w każdej iteracji należy zwiększać pierwszą liczbę w parze i zmniejszać drugą. Taki zabieg gwarantuje, że suma liczb w parze zawsze wynosi a. Jeśli w dowolnej iteracji obie liczby będą pierwsze to wtedy a jest liczbą Goldbacha.

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

(1.) Dla podanej liczby a zwróć czy jest liczbą Goldbacha. (2.) Pierwsza liczba w parze musi być mniejsza niż druga, ponieważ po przekroczeniu pewnej liczby byłyby rozpatrywane te same pary zapisane wstecz. Następnie dla każdej takiej wyliczonej pary: (3.) należy sprawdzić czy obie liczby są pierwsze. (4.) Jeśli są to należy zwrócić prawdę. (7.) Jeśli jednak pętla for się zakończy bez prawdy należy zwrócić fałsz.

Rozkład

W celu upewnienia się czy funkcja czyGoldbach() zwraca prawidłowe wyniki oraz z ciekawości z jakich liczb pierwszych składa się liczba Goldbacha warto napisać funkcję rozlozGoldbach(), która wypisze na ekran liczby pierwsze z których składa się dana liczba a. Jeśli jednak liczba nie jest liczbą Goldbacha to zostanie wypisany odpowiedni komunikat.

  1. void rozlozGoldbach(int a) {
  2.   for (int i = 2; i <= a - i; i++) {
  3.     if (czyPierwsza(i) && czyPierwsza(a - i)) {
  4.       cout << a << " = " << i << " + " << a - i << "\n";
  5.       return;
  6.     }
  7.   }
  8.   cout << a << " nie jest liczba Goldbacha\n";
  9. }

Zasada działania funkcji rozlozGoldbach() jest identyczna co czyGoldbach().

Wszystkie rozkłady

Jednak jak pewnie można się spodziewać jedna liczba Goldbacha może mieć kilka różnych sposobów rozkładu, dlatego warto napisać funkcję rozlozGoldbachWszystkie(), która wypisze wszystkie rozkłady danej liczby a na dwie liczby pierwsze.

Przykładem liczby Goldbacha, który ma kilka rozkładów jest liczba 102, którą można rozłożyć na następujące pary: {(5, 97), (13, 89), (19, 83), (23, 79), (29, 73), (31, 71), (41, 61), (43, 59)}.

  1. void rozlozGoldbachWszystkie(int a) {
  2.   bool znalezione = false;
  3.   cout << a;
  4.   for (int i = 2; i <= a - i; i++) {
  5.     if (czyPierwsza(i) && czyPierwsza(a - i)) {
  6.       cout << " = " << i << " + " << a - i;
  7.       znalezione = true;
  8.     }
  9.   }
  10.   if(!znalezione)
  11.     cout << " nie jest liczba Goldbacha";
  12.   cout << endl;
  13. }

(2.) Zadeklaruj zmienną pomocniczą, która zapamięta czy liczba ma chociaż jeden rozkład. (3.) Wypisz liczbę, a następnie (4. - 9.) poszukaj jej rozkładu. (5.) Jeśli rozkład zostanie znaleziony: (6.) wypisz go i (7.) odznacz, że istnieje chociaż jeden rozkład danej liczby a. Na koniec (8.) jeśli okaże się, że nie został wypisany ani jeden rozkład to (9.) wypisz komunikat, że a nie jest liczbą Goldbacha.

Testowanie funkcji

W celu wypisania wszystkich rozkładów liczby a wystarczy poniższa funkcja main():

  1. int main() {
  2.   int a;
  3.   cout << "Podaj liczbe do sprawdzenia:\n";
  4.   cin >> a;
  5.   rozlozGoldbachWszystkie(a);
  6.   system("pause");
  7.   return 0;
  8. }

Zadania

Zadanie 1

Napisz funkcję podajnGoldbacha(), która wypisze na ekran n liczb Goldbacha począwszy od a (włącznie). Liczby n i a mają zostać wczytane przez program od użytkownika.

Przykładowo dla n = 10 oraz a = 100 program powinien wypisać na ekran:

  1. 100, 102, 103, 104, 105, 106, 108, 109, 110, 111