Kurs maturalny z języka angielskiego!
kurs-maturalny-jezyk-angielski

PROGRAMOWANIE I ALGORYTMY

Zajęcia maturalne z informatyki
Olimpiada Informatyczna Juniorów
    Prowadzący: Marcin Kasprowicz
  • właściciel serwisu algorytm.edu.pl
  • wrzesień 2024 — start zajęć
  • czytaj więcej

Liczby doskonałe


powrót

Liczba doskonała (definicja) to taka liczba naturalna, której suma jej dzielników właściwych (bez niej samej) jest jej równa. 

Taką liczbą jest np. 6, ponieważ

$$D_6=\{1, 2, 3\}$$ oraz $$ 6 = 1+2+3$$

lub 28

$$D_{28}=\{1, 2, 4, 7, 14\}$$ oraz $$ 28 = 1+2+4+7+14$$

Kilka kolejnych liczb doskonałych

$$6,\ 28,\ 496,\ 8128,\ 33550336,\ 8589869056,\ 137438691328$$

Strategia algorytmu

Siłowe rozwiązanie dla liczby n polega na sprawdzeniu wszystkich liczb z przedziału [1..n] i wyłonieniu z nich tych, które są dzielnikami liczby n. Np. dla liczby 28 sprawdzamy kolejno liczby 1, 2, 3, ..., 28 i jeśli któraś dzieli bez reszty liczbę 28, dodajemy ją do sumy dzielników. Dla dużych liczb ten algorytm staje się bardzo powolny. Warto zauważyć, że jeśli znajdziemy jeden dzielnik, to do pary otrzymujemy drugi (wyjątek stanowią liczby kwadratowe), np. dla liczby 28 mamy:

$$1$$ oraz $$\frac{28}{1}=28$$ 

$$2$$ oraz $$\frac{28}{2}=14$$ 

$$4$$ oraz $$\frac{28}{4}=7$$ 

Dalej nie szukamy, ponieważ dzielniki będą się powtarzały. Liczby, które musimy sprawdzić, czy są potencjalnymi dzielnikami będą zawierać się w przedziale $$[1..[\sqrt{n}]]$$, a więc dla liczby 28 jest to $$[1..[\sqrt{28}]]=[1..5]$$. Dla liczby kwadratowej, jej "środkowy" dzielnik zliczamy tylko raz. Oczywiście dla liczb doskonałych nie bierzemy pod uwagę dzielnika, który jest badaną liczbą.

Sprawdzanie, czy podana liczba jest doskonała

//algorytm.edu.pl
#include<iostream>
#include<cmath>
using namespace std;

bool czy_doskonala(int n)
{
	int s = 1, p = sqrt(n);
	for(int i=2; i<=p; i++)
		if(n%i == 0)
	//dodajemy do sumy dwa dzielniki
			s+= i + n/i;
	
	//jesli mamy do czynienia z liczbą kwadratową
	//to dwa razy dodalismy jej pierwiastek
	//więc musimy go raz odjąć
	if(n == p*p) s-=p;
	
	//jesli suma dzielników jest równa danej liczbie
	//do podana liczba jest doskonała
	if(n == s) return 1;
	
	return 0;	
}

int main()
{
	int n;
	cout<<"Podaj liczbę: ";
	
	cin>>n;
	
	if(czy_doskonala(n))
		cout<<"Liczba "<<n<<" jest doskonała";
	else
		cout<<"Liczba "<<n<<" nie jest doskonała";
	
	return 0;
}