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ż:

• dzielniki liczby 284: 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110, a ich suma to 220,
• dzielniki liczby 220: 1, 2, 4, 71, 142, a ich suma to 284.

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:

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

• Kod źródłowy Implementacja

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.

• Kod źródłowy Zadanie 1