👤

Cerinţa
Să se scrie un program care afișează divizorii comuni ai două numere naturale citite de la tastatură.

Date de intrare
Programul citește de la tastatură două numere naturale a și b.

Date de ieşire
Programul afișează pe ecran, în ordine crescătoare, divizorii comuni ai numerelor a și b, separați printr-un spațiu.

Restricţii şi precizări
0 < a, b < 1.000.000.000
Exemplu1:
Intrare

24 36
Ieșire

1 2 3 4 6 12


Răspuns :

#include <iostream>
using namespace std;
int a, b, d, i, r;
int main()
{
// Cautam toti divizorii lui a, si daca sunt divizori
// si pentru b, ii afisam
// observam ca divizori comuni ai lui a si b vor divide si cmmdc al lor
// calculam cmmdc si afisam divizorii acestuia

cin >> a >> b;
d = a;
i = b;

//vom calcula cmmdc pentru a, b, folosind algoritmul lui Euclid.

//stim ca numerele sunt nenule
r=d % i;
while(r)
{
d = i;
i = r;
r = d%i;
}
//rezultatul este ultimul impartitor, adica i.

// afisam divizorii lui b (cmmdc-ul calculat)
for(d=1 ; d<=i; d++)
if(i % d == 0)
cout << d << " ";

return 0;
}