Divizorii unui număr. Metoda eficientă

Enunț

Se citeşte un număr natural n. Să se scrie un algoritm eficient care afișează toți divizorii numărului n.

Un număr natural d este divizor al lui n dacă și numai dacă n%d=0 (n se împarte exact la d sau, altfel spus, restul împărțirii lui n la d este egal cu 0).

Argument matematic

Simetria Divizorilor

Dacă d este un divizor al lui n, atunci și n/d​ este un divizor. Aceasta se datorează faptului că dacă n se împarte exact la d, rezultatul q=n/d​ este și el un divizor al lui n.
Datorită faptului că divizorii unui număr apar în perechi și că unul din fiecare pereche este întotdeauna mai mic sau egal cu radical(n)​, este suficient să căutăm divizorii unui număr până la radical(n).

Exemplu

Fie n=36. Divizorii săi sunt:
1,2,3,4,6,9,12,18,36
Observăm că:
1×36=36
2×18=36
3×12=36
4×9=36
6×6=36 (în acest caz, 6 este exact radical(36)​)

De aici se observă că pentru fiecare divizor d mai mic decât radical(36)​, există un divizor 36/d​ mai mare decât radical(36)​. Când ajungem la radical(n)​, divizorul se va repeta dacă n este un pătrat perfect (cum este cazul lui 6 pentru n=36)

Algoritmul în limbaj pseudocod

n,d întreg
citeşte n
pentru d ← 1, sqrt(n) execută
| dacă n % d = 0 atunci
| |  scrie d
| |  dacă d != n/d atunci
| |    scrie n/d
| |▄
|▄

Algoritmul în limbaj de programare C/C++

/**************************************************************

divizorii unui numar - metoda eficienta

***************************************************************/

#include <iostream>
#include <cmath>

using namespace std;

int main() {
	int n;

	cout << "Introduceti un numar: ";
	cin >> n;

	cout << "Divizorii numarului " << n << " sunt: ";

	for (int d = 1; d <= sqrt(n); d++) {
		
		if (n % d == 0) {
		
			cout << d << " "; // d este un divizor
		
			if (d != n / d) {
			
				cout << n / d << " "; // n / d este un alt divizor
			}
		}
	}

	cout << endl;

	return 0;
}