Programowanie i algorytmy

KONKURS FRAKTAL

fraktal

VII edycja konkursu programistycznego

FRAKTAL

8-9 kwietnia 2017

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ż

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

lub 28

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

Kilka kolejnych liczb doskonałych

{tex}6,\ 28,\ 496,\ 8128,\ 33550336,\ 8589869056,\ 137438691328{/tex}

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:

{tex}1{/tex} oraz {tex}\frac{28}{1}=28{/tex} 

{tex}2{/tex} oraz {tex}\frac{28}{2}=14{/tex} 

{tex}4{/tex} oraz {tex}\frac{28}{4}=7{/tex} 

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 {tex}[1..[\sqrt{n}]]{/tex}, a więc dla liczby 28 jest to {tex}[1..[\sqrt{28}]]=[1..5]{/tex}. 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

#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";
 
  cin.ignore();
  cin.get();
 
  return 0;
}