public class GCD_2 {
	// aとbの最大公倍数を戻すメソッド
	// 値が取得できない場合0を戻す
	static int gcd( int a, int b )
	{
		// 両方の値が0以下なら0を戻す
		if ( ( 0 >= a ) && ( 0 >= b ) ) return 0;

		// 両方の値が同じならaを戻す
		if ( a == b ) return a;

		// 片方の値が0以下なら0を戻す
		if ( ( 0 >= a ) || ( 0 >= b ) )
			return Math.max( a, b );

		// 最大公約数の初期値
		int ans = 1;

		// 最大公約数を求めるループ
		for ( ; ; ) {
			// 片方の値が1以下ならループを抜ける
			if ( ( 1 >= a ) || ( 1 >= b ) ) break;

			// ２以上の１番小さい公約数を求める
			int cd = 1;
			int min= Math.min( a, b );
			for ( int i = 2; i <= min; i ++ ) {
				if ( 0 == ( a % i ) ) {
					// aはiで割り切れた
					if ( 0 == ( b % i ) ) {
						// bはiで割り切れた
						// 最も小さい公約数
						cd = i;
						break;
					}
				}
			}

			// ２以上の公約数がなかったらループを抜ける
			if ( 1 == cd ) break;

			// 最大公約数を掛け合わせる
			ans *= cd;

			// ２つの自然数を約数で割る
			a /= cd;
			b /= cd;
		}

		return ans;
	}


	// メイン
	public static void main( String[] args ) {
		// ２つの変数を宣言
		int a, b;

		// ８と１２の最大公約数
		a = 8;
		b = 12;
		System.out.println( a + "と" + b + "の最大公約数は、" + gcd( a, b ) );

		// １３と４の最大公約数
		a = 13;
		b = 4;
		System.out.println( a + "と" + b + "の最大公約数は、" + gcd( a, b ) );

		// 144と32の最大公約数
		a = 144;
		b = 32;
		System.out.println( a + "と" + b + "の最大公約数は、" + gcd( a, b ) );

		// ０と１０の最大公約数
		a = 0;
		b = 10;
		System.out.println( a + "と" + b + "の最大公約数は、" + gcd( a, b ) );

		// ０と０の最大公約数
		a = 0;
		b = 0;
		System.out.println( a + "と" + b + "の最大公約数は、" + gcd( a, b ) );
	}
}