Based on the use of Euclidean algorithm

Euclidean algorithm is called division, used to find the common factor of two known natural Numbers m and n. Combine the procedure to explain the specific case of division.

First, the recursive implementation:

int getcd(int m,int n)
 {
     if (m < 0 || n <0) {
         return 0;
     }
     if(m < n)
     {
         int t = m;
         m = n;
         n = t;
     }
     if(m % n)
     {
         return getcd(n,(m % n));
     }
     else 
     {
         return n;
     }
 }

1. The two input natural Numbers m > N has a remainder r such that 0< = r < n

2. If r is 0, n is the result and returns directly

3. If r is not 0, then m=n is assigned, and n=r is reexecuted from step 1

The definition of the common factor of two natural Numbers explains the conditions under which the calculated results are produced. If the remainder calculated in step 1 r = 0, the smaller number is a common factor. If r! =0 then the relation between the natural Numbers m and n can be expressed as: m = kn + r (where k is the natural number). The equation can prove that any number divisible into m must be divisible into n and r. The equation can be further deformed as: r = m-kn, which means that any number divisible into m and n must also be divisible into r. In other words, the set of Numbers that are divisible into m and n is the same as the set of Numbers that are divisible into n and r. So the division method works.
 

Release another version of the loop that implements Euclid's algorithm.

int getcd2(int m,int n)
 {
     if (m < 0 || n <0) {
         return 0;
     }
     if(m<n)
     {
         int t=m;
         m=n;
         n=t;
     }
     int cd = 1;
     while(1){
         int r = m % n;
         if(0==r)
         {
             cd = n;
             break;
         }
         else {
             m=n;
             n=r;
         }
     }
     return cd;
 }