package Course_Codes;

import java.util.Scanner;

//求两个数的最大公约数
public class 求最大公约数 {

	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int a=sc.nextInt();
		int b=sc.nextInt();
		System.out.println("欧几里得："+Gcd1(a,b));
		System.out.println("递归："+Gcd(a,b));

	}
	//Gcd=最大公约数
	public static int Gcd(int a,int b) {
		return b==0?a:Gcd(b,a%b);
	}
	
	public static int Gcd1(int a,int b) {
		while(b>0) {
			int temp=a%b;
			a=b;
			b=temp;//Gcd(a,b)=>Gcd(b,a%b)		
		}
		return a;
	}
}