Divizorii unui numar



Metoda naiva


#include <iostream>

using namespace std;

int main()
{
   int nr;
   cin>>nr;

   //toti divizorii
   for(int d=1;d<=nr;d++)
      if(nr%d==0)
         cout<<d<<' ';
   cout<<'\n';
   
   //divizorii proprii
   for(int d=2;d<=nr/2;d++)
      if(nr%d==0)
         cout<<d<<' ';
}


Explicatie:

- citim numarul
- in variabila d vom parcurge toate numerele de la 1 la nr si vom verifica daca acestea sunt divizori ai lui nr




Metoda eficienta

#include <iostream>

using namespace std;

int main()
{
   int nr;
   cin>>nr;

   //toti divizorii
   if(nr==1)
      cout<<nr;
   else
   {
      int d;
      //le vom afisa ca perechi
      cout<<1<<' '<<nr<<' '; 
      for(d=2;d*d<nr;d++) //d*d<n inseamna ca mergem pana la < sqrt(nr)
      if(nr%d==0)
         cout<<d<<' '<<nr/d<<' '; //d * nr/d = nr
      if(d*d==nr)
         cout<<d; //vom afisa doar o data, deaorece nu mai avem pereche
   }
   cout<<'\n';
   
   //divizorii proprii
   int d;
   for(d=2;d*d<nr;d++)
      if(nr%d==0)
         cout<<d<<' '<<nr/d<<' ';
   if(d*d==nr)
      cout<<d;
}

Explicatie:

- citim numarul
- in variabila d vom parcurge toate numerele de la 2 la sqrt(nr) si vom verifica daca acestea sunt divizori ai lui nr
- le vom afisa drept perechi, deoarece d * nr/d va avea rezultat nr
- trebuie sa fim atenti in momentul in care numarul este patrat perfect pentru a nu afisa un divizor de 2 ori