递归实现最大公约数(辗转相除法)

首先说下最大公约数是个什么东西,我刚才已经忘记了不知道这是个什么东东了.

最大公约数 指两个或多个整数共有约数中最大的一个。

辗转相除法

辗转相除法：辗转相除法是求两个自然数的最大公约数的一种方法

例如，求（319，377）：

∵ 319÷377=0（余319）

∴（319，377）=（377，319）；

∵ 377÷319=1（余58）

∴（377，319）=（319，58）；

∵ 319÷58=5（余29）

∴ （319，58）=（58，29）；

∵ 58÷29=2（余0）

∴ （58，29）= 29；

∴ （319，377）=29。

很容易发现,用第一个数去除以第二个数,获取到余数,然后再用第二个数去除以余数。直到余数为0就求到了最大公约数

可以得出以下规律:

代码:

import java.util.Scanner;

public class MaxCommonDIvisor {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int a = in.nextInt();
		int b = in.nextInt();
		
		int c = fun(a,b);
		System.out.println(c);
		
	}
	public static int fun(int a,int b)
	{
		if(b<=a && b == 0)
		{
			return a;
		}else if(a<b)
		{
			return fun(b,a);
		}else
		{
			return fun(b,a%b);
		}
		
	}
}