Question

Salut!
Atunci cand caut numarul de numere prime intre ele folosind algoritmul lui Eucled, cel cu scaderea, de ce la final pun conditia if(x[i]==1 contor++;??
Nu inteleg logica din spate.
Va pun un cod sursa sa stiti excat la ce ma refer.
while (x[i]!=aux)
{
if (x[i]>aux)
{

x[i]=x[i]-aux;

}
else
aux=aux-x[i];
}
if (x[i]==1)
contor++;
}

Answer 1

#include <iostream>

using namespace std;

int main()

{

   int a, b;

   // a - primul numar

   // b - al doilea numar

   // doua numere sunt prime intre ele dacă cel mai mare divizor comun al lor este 1

   cin >> a;

   cin >> b;

   while (a != b){

       if (a > b)

           a = a - b;

       else

           b = b - a;

   }

   if (a == 1)

       cout << "Sunt prime intre ele";

   else

       cout << "Nu sunt prime intre ele";

   

   // O mica explicatie a algoritmului :

   

   /*

       a = 24;

       b = 6;

       cat timp (24 diferit de 6){

           daca (24 este mai mare decat 6)

               atunci a = 24 - 6 => a = 18;

           altfel

               b = b - a;

       }

       a = 18;

       b = 6;

       tot primul caz este (a > b), deci a = a - b din nou

       a = 12;

       b = 6;

       din nou, tot a > b

       a = a - b;

       a = 6;

       b = 6;

       cele doua nu mai sunt diferite iar structura repetitiva "while" se opreste;

       la final testam daca a == 1 sau b == 1, pe care vrem, deoarece ele o sa fie egale intotdeauna

       

       

       

       Alt ex:

       a = 24;

       b = 35;

       Aici avem b > a, deci b = b - a;

       b = 35 - 24 = > b = 11;

       Acum, a > b = > a = a - b = > a = 24 - 11 = 13;

       Tot a > b, = > a = a - b = > a = 13 - 11 = 2;

       Acum, b > a, = > b = b - a = > b = 11 - 2 = 9;

       b > a = > b = 9 - 2 = 7;

       b > a = > b = 7 - 2 = 5;

       b > a = > b = 5 - 2 = 3;

       b > a = > b = 3 - 2 = 1;

       

       Deci 24 si 35 sunt prime intre ele, iar 24 si 12 nu sunt. Sper ca ai inteles.

       

   */

   

   return 0;

}