Strona główna » Algorytmy » Teoria Liczb » Liczby Zaprzyjaźnione

Liczby Zaprzyjaźnione

Definicja

Liczby zaprzyjaźnione to para różnych liczb naturalnych a i b. Suma dzielników właściwych liczby a wynosi b i analogicznie suma dzielników liczby b wynosi a.

Pierwszą parę liczb zaprzyjaźnionych podał Pitagoras: 220 i 284, ponieważ:

Do tej pory nie rozstrzygnięto ile jest liczb zaprzyjaźnionych oraz czy istnieje para o różnej parzystości. Oto pierwsze 5 par liczb zaprzyjaźnionych:

Liczba ALiczba B
220284
1 1841 210
2 6202 924
5 0205 564
6 2326 368

Każda liczba doskonała jest zaprzyjaźniona sama ze sobą.

Implementacja

Funkcja pomocnicza

Podczas kodowania pomocna będzie funkcja, która dla podanej liczby n obliczy sumę ich dzielników:

  1. int sumaDzielnikow(int n){
  2.   int suma = 1;
  3.   for(int i = 2; i < n; i++)
  4.     if(n % i == 0)
  5.       suma += i;
  6.   return suma;
  7. }

(1.) Funkcja zwróci nam liczbę całkowitą, która będzie sumą wszystkich dzielników właściwych liczby n. (2.) Zmienną suma ustalamy na 1, ponieważ dzieli każdą liczbę. (3.) Szukamy dzielników liczby n w zakresie [2, n/2] i (4.) jeśli i-ta liczba dzieli n to dodajemy ją do zmiennej suma. Po zakończeniu pętli (5.) zwracamy suma, która jest sumą dzielników liczby n.

Czy liczby zaprzyjaźnione?

Funkcja będzie przyjmowała dwa argumenty: liczbę a oraz b. Wynikiem funkcji będzie wartość logiczna.

  1. bool czyZaprzyjaznione(int a, int b){
  2.   return (a == sumaDzielnikow(b) && b == sumaDzielnikow(a) && a != b);
  3. }

(2.) Zwracamy wynik warunków nierówności liczb a i b, czy a to suma dzielników właściwych b oraz czy b to suma dzielników właściwych a.

Zaprzyjaźniona do danej liczby

Nasza funkcja będzie teraz przyjmowała tylko jeden argument: liczbę całkowitą a. Nasze zadanie polega na zwróceniu liczby do niej zaprzyjaźnionej. Jeśli jednak taka liczba nie istnieje to zwracamy 0.

  1. int podajZaprzyjazniona(int a){
  2.   int b = sumaDzielnikow(a);
  3.   return (a == sumaDzielnikow(b) && a != b) ? b : 0;
  4. }

(2.) Sumujemy liczbę dzielników danej liczby a i zakładamy, że jest to liczba bliźniacza b. (3.) Liczbę b zwracamy tylko, gdy a to suma dzielników b oraz a jest różne od b. Jeśli któryś z warunków nie jest spełniony to zwracamy 0.

Pierwsze n liczb zaprzyjaźnionych

Będziemy przeszukiwać kolejne liczby i wyliczać liczbę zaprzyjaźnioną. Funkcja nie będzie nic zwracać, ponieważ wyniki będziemy wypisywać bezpośrednio na konsole.

  1. void podajnZaprzyjaznionych(int n){
  2.   int t, i = 220;
  3.   while(n > 0){
  4.     if((t = podajZaprzyjazniona(i)) != 0 && i < t){
  5.       cout << i << " z " << t << endl;
  6.       n--;
  7.     }
  8.     i++;
  9.   }
  10. }

(2.) Deklarujemy zmienne t - do buforowania wyliczonej liczby zaprzyjaźnionej oraz i do przechowywania, którą liczbę sprawdzamy tj. pierwszą liczbę z pary liczb zaprzyjaźnionych. (3.) Dany argument n traktujemy jako odliczanie i wykonujemy pętle while dopóki n > 0. Dla każdego i wyliczamy liczbę zaprzyjaźnioną i sprawdzamy czy wynik jest różny od 0 - czyli czy istnieje liczba zaprzyjaźniona. Musimy jeszcze sprawdzić czy sprawdzana liczba i jest mniejsza od wyliczonej t (albo odwrotnie), bo będziemy wypisywać każdą parę liczba zaprzyjaźnionych dwukrotnie - w postaci a x b oraz b x a. Jeśli znajdziemy liczbę zaprzyjaźnioną to (4.) wypisujemy parę liczb oraz (5.) zmniejszamy ile jeszcze par liczb zaprzyjaźnionych szukamy.

Testowanie programu

Poniższa funkcja main() wczyta od użytkownika dwie liczby a i b, a potem wypisze czy liczby te są zaprzyjaźnione. Następnie na ekran zostanie wypisane pierwsze pięć par liczb zaprzyjaźnionych.

  1. int main () {
  2.   int a, b;
  3.   cin >> a >> b;
  4.   cout << (czyZaprzyjaznione(a, b) ? "TAK" : "NIE") << endl;
  5.   int t = podajZaprzyjazniona(a);
  6.   if(t == 0){
  7.     cout << a << " nie jest liczba zaprzyjazniona" << endl;
  8.   } else {
  9.     cout << "l. zaprzyjazniona z " << a << " to " << t << endl;
  10.   }
  11.   cout << "pierwsze 5 par liczb zaprzyjaznionych to:\n";
  12.   podajnZaprzyjaznionych(5);
  13.   system("pause");
  14.   return 0;
  15. }

Zadania

Zadanie 1

Dopisz funkcję podajZaprzyjazniona2(), aby korzystała z funkcji czyZaprzyjaznione(). Funkcja powinna zwrócić wartość 0 jeśli nie ma liczby zaprzyjaźnionej lub wartość liczby zaprzyjaźnionej

Zadanie 2

Dopisz funkcję podajnZaprzyjaznionychod() na podstawie podajnZaprzyjaznionych(), która rozpocznie wypisywanie par liczb zaprzyjaźnionych większych od określonej liczby od. Nagłówek funkcji powinien wyglądać tak:

  1. void podajnZaprzyjaznionychod(int n, int od){

Gdzie n określa ile kolejnych par liczb zaprzyjaźnionych o obu liczbach w parze większych lub równych od od ma być wypisanych.