Divizorii comuni a doua numere



Metoda naiva

#include <iostream>

using namespace std;

int main()
{
   int a, b;
   cin>>a; //primul numar
   cin>>b; //al doilea numar
   //le vom modifica astfel incat a sa fie cel mai mic dintre cele 2
   if(b<a)
   {
      int aux=a;
      a=b;
      b=aux;
   }
   int d;
   //vom considera toti divizorii: proprii si improprii
   for(d=1;d<=a;d++)
      if(a%d==0 && b%d==0)
         cout<<d<<' ';
}

Explicatie:

- citim cele 2 numere: a si b
- le ordonam pentru a parcurge for-ul de divizori pana la cel mai mic
- vom verifica pentru fiecare numar de la 1 la cel mai mic dintre cele 2 numere daca se imparte la a si b




Metoda eficienta

#include <iostream>

using namespace std;

int main()
{
   int a, b;
   cin>>a; //primul numar
   cin>>b; //al doilea numar
   //le vom modifica astfel incat a sa fie cel mai mic dintre cele 2
   if(b<a)
   {
      int aux=a;
      a=b;
      b=aux;
   }
   int d;
   //vom considera toti divizorii: proprii si improprii
   if(a==1) //nu exista alti divizori in afara de 1
      cout<<1;
   else
   {
      cout<<1<<' ';
      if(b%a==0)
         cout<<a<<' ';
      for(d=2;d*d<=a;d++)
         if(a%d==0 && b%d==0)
         {
            cout<<d<<' ';
            if(b%(a/d)==0 && d*d!=a)
               cout<<a/d<<' ';
         }
   }
}

Explicatie:

- citim cele 2 numere: a si b
- le ordonam pentru a parcurge for-ul de divizori pana la cel mai mic
- vom verifica pentru fiecare numar de la 2 la sqrt(a) daca acesta este divizor pentru ambele numere
- in caz afirmativ, vom verifica daca elementul care corespunde perechii a/d este divizor pentru b, deoarece pentru a este clar ca e
- mai trebuie verificat sa nu fi ajuns la sqrt(a) si sa nu afisam divizorul de 2 ori