Lập trình

Tìm ước chung lớn nhất của 2 số nguyên dương bằng cách phân tích thừa số nguyên tố

Thuận toán

Lặp	i	A	B	UCLN
	2	180	840	1
1	2	90	420	1 *2
2	2	45	210	1 *2*2
3	2	45	105	1 *2*2
4	3	15	35	1 *2*2*3
5	3	5	35	1 *2*2*3
6	4	5	35	1 *2*2*3
7	5	1	7	1*2*2*3*5= 60

 

void UCLN(int A, int B){

      cout<<"UCLN("<

      int s = 1;

      int i=2;

      while(A!=1 && B!=1)

            if(A%i==0 && B%i==0){

                  cout<

                  s = s * i; A = A/i; B = B/i;

            }

            else if(A%i==0 && B%i!=0){

                        A = A/i;

                   } else if(A%i!=0 && B%i==0){

                                    B = B/i;

                              }else i++;

      cout<<"\b ="< }