题目： 使用欧几里得算法求两个数的最大公因式。

欧几里得算法：
1.如果r是a除以b的余数，那么a与b的最大公因数和b与r的最大公因数相等，使用公式表示为：gcd(a,b)=gcd(b,r).
2.使用欧几里得算法，可将两个大整数的最大公约数逐渐转化为两个较小整数的最大公约数，例如gcd(36,16)=gcd(16,4)=gcd(4,0)=4. 可见36和20的最大公约数为4.

java代码：

package greatestCommonDivisor;

import java.util.Scanner;

public class greatestCommonDivisor {

    public static void main(String[] args) {
        System.out.println("please input two numbers:");
        Scanner in = new Scanner(System.in);
        int a = in.nextInt();
        int b = in.nextInt();
        gcd(a,b);
    }

    public static void gcd(int a,int b) {
        int x = a;
        a = b;
        b = x%b;
        if(b==0) {
            System.out.println("the greatest common divisor is:"+a);
        } else {
           gcd(a,b);
        }
    }
}

• 1、该算法转化关系很容易，主要是需要考虑迭代。在第二次迭代时，a=b，b=a%b.可是这时候不论先执行那个语句，a和b的值都会被改变，导致结果出错，所以需要借助另一个变量x寄存其中的一个数。
• 2、迭代终止的条件为第二个数变为0.此时输出a的值即为最大公因式。
• 3、不用考虑输入的值a大还是b大，因为gcd(16,36)=gcd(36,16).即如果a<b,只需多进行一次迭代就会交换两个数的位置。