【Java】ユークリッドの互除法

この記事は、「新・明解Javaで学ぶアルゴリズムとデータ構造」を読んで学んだことを、個人的な備忘録目的でまとめています。

ただし、本を参考にして自分なりに構成やコードを変更しているためご注意ください。
アルゴリズムの詳細や解説は是非参考書をお手に取って読まれてください。

【リンク紹介】
・Javaで学ぶアルゴリズムとデータ構造
・これまで書いたシリーズ記事一覧

基本用語確認

【Java】階乗を参照。

ユークリッドの互除法

ユークリッドの互除法の実装

ユークリッドの互除法を用いた最大公約数を求める実装は次の通り。

//--- 整数値x, yの最大公約数を求めて返却 ---//
static int gcd(int x, int y) {
  if (y == 0)              // ①
    return x;              // ②
  else
    return gcd(y, x % y);  // ③
}

アルゴリズムのイメージ図

30と18の最大公約数を求める。

つまり

ユークリッドの互除法の利用例

import java.util.Scanner;

// ユークリッドの互除法によって最大公約数を求める
public class EuclidGCD {
  
  //--- 整数値x, yの最大公約数を求めて返却 ---//
  static int gcd(int x, int y) {
    if (y == 0)
      return x;
    else
      return gcd(y, x % y);
  }
  
  public static void main(String[] args) {
    Scanner stdIn = new Scanner(System.in);
    
    System.out.println("二つの整数の最大公約数を求めます。"); 
    System.out.print("整数を入力せよ：");
    int x = stdIn.nextInt();
    
    System.out.print("整数を入力せよ：");
    int y = stdIn.nextInt();
    
    System.out.println("最大公約数は" + gcd(x, y) + "です。");
  }
}

実行結果

二つの整数の最大公約数を求めます。
整数を入力せよ：30
整数を入力せよ：18
最大公約数は6です。

$\bf{\textcolor{red}{記事が役に立った方は「いいね」を押していただけると、すごく喜びます \ 笑}}$
ご協力のほどよろしくお願いします。