Număr perfect
Enunț
Se citeşte un număr natural n. Să se verifice dacă n este sau nu un număr perfect.
Exemplu
Dacă n = 6, atunci algoritmul va afişa DA. Numărul n = 6 este perfect, deoarece 2 × 6 = 1 + 2 + 3 + 6
Dacă n = 8, atunci algoritmul va afişa NU. Numărul n = 8 nu este perfect, deoarece 2 × 8 != 1 + 2 + 4 + 8.
Varianta 1
Descrierea metodei de rezolvare
Putem folosi proprietatea “Un număr perfect este un număr întreg pozitiv care este egal cu suma divizorilor săi pozitivi diferiți de el însuși.“
Pasul 1: Citim numărul n.
Pasul 2: Inițializăm variabila s cu 0. (în s vom calcula suma divizorilor lui n diferiți de n)
Pasul 3: Calculăm în s suma tuturor divizorilor lui n diferiți de n
Pasul 4: Dacă n = s atunci n este număr perfect și afișăm "DA"
altfel n nu este număr perfect și afișăm "NU"Algoritmul în limbaj pseudocod
n,d,s întreg
citeşte n
s ← 0
pentru d ← 1, n-1 execută
| dacă n % d = 0 atunci
| | s ← s + d
| |▄
|▄
dacă n = s atunci
| scrie “DA”
|altfel
| scrie “NU”
|▄
Algoritmul în limbaj de programare C/C++
/***********************************************************
numar perfect - V1
************************************************************/
#include <iostream>
using namespace std;
int main() {
int n, d, s;
cout << "Introduceti un numar: ";
cin >> n;
s = 0;
for (d = 1; d <= n-1; d++) {
if (n % d == 0) {
s += d; // adaugam divizorul la suma
}
}
// Verificam daca suma divizorilor este egala cu numarul
if (n == s) {
cout << "DA" << endl; // n este un numar perfect
} else {
cout << "NU" << endl; // n nu este un numar perfect
}
return 0;
}Varianta 2 – algoritm eficient
Descrierea metodei de rezolvare
Putem folosi proprietatea “Un număr natural n este perfect dacă dublul său este egal cu suma divizorilor săi.“
Pasul 1: Citim numărul n.
Pasul 2: Inițializăm variabila s cu 0. (în s vom calcula suma divizorilor)
Pasul 3: Calculăm în s suma tuturor divizorilor lui n
Pasul 4: Dacă 2*n = s atunci n este număr perfect și afișăm "DA"
altfel n nu este număr perfect și afișăm "NU"Algoritmul în limbaj pseudocod
n,d,s întreg
citeşte n
s ← 0
pentru d ← 1, sqrt(n) execută
| dacă n % d = 0 atunci
| | s ← s + d
| | dacă d != n/d atunci
| | s ← s+ n/d
| |▄
|▄
dacă 2*n = s atunci
| scrie “DA”
|altfel
| scrie “NU”
|▄
Algoritmul în limbaj de programare C/C++
/***********************************************************
numar perfect - V2 algoritm eficient
************************************************************/
#include <iostream>
#include <cmath>
using namespace std;
int main() {
int n, d, s;
cout << "Introduceti un numar: ";
cin >> n;
s = 0;
for (d = 1; d <= sqrt(n); d++) {
if (n % d == 0) {
s += d; // adaugam divizorul la suma
if (d != n / d) {
s += n / d; // adaugam si celalalt divizor (n/d) daca este diferit
}
}
}
// Verificam daca suma divizorilor este dublul numarului
if (2 * n == s) {
cout << "DA" << endl; // n este un numar perfect
} else {
cout << "NU" << endl; // n nu este un numar perfect
}
return 0;
}
Observație
Acest algoritm folosește metoda eficientă de determinare a divizorilor unui număr.