2020.03.23
数学
ユークリッド互除法
ユークリッド互除法は、以下の性質を利用して最大公約数を計算します。
等式：a = b × q + rにおいて、
例として、a = 144、b = 32の場合を考えてみます。
等式：a = b × q + rに値を代入すると、
144 = 32 × q + r
整数のqとrを求めると
q = 4
r = 16
となります。
bをa、rをbにし、等式に代入すると
a = 32
b = 16
となり、等式は
32 = 16 × q + r
となります。
整数のqとrを求めると
q = 2
r = 0
Javaソースコード
GCD_3.java
001 002 003 004 005 006 007 008 009 010 011 012 013 014 015 016 017 018 019 020 021 022 023 024 025 026 027 028 029 030 031 032 033 034 035 036 037 038 039 040 041 042 043 044 045 046 047 048 049 050 051 052 053 054 055 056 057 058
public class GCD_3 { // 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 r = a % b; while ( 0 != r ) { a = b; b = r; r = a % b; } return b; } // メイン 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 ) ); } }
コンパイル ソースコードが「ANSI」の場合
C:\talavax\javasample>javac -encoding sjis GCD_3.java
コンパイル ソースコードが「UTF-8」の場合
C:\talavax\javasample>javac GCD_3.java
実行
C:\talavax\javasample>java GCD_3
出力結果
8と12の最大公約数は、4 13と4の最大公約数は、1 144と32の最大公約数は、16 0と10の最大公約数は、10 0と0の最大公約数は、0
２つの値の両方が０の場合は０を戻します。
Javaソースコードの解説
001
public class GCD_3 {
クラス名を、GCD_3としています。
002 003 004 005
// aとbの最大公倍数を戻すメソッド // 値が取得できない場合0を戻す static int gcd( int a, int b ) {
006 007
// 両方の値が0以下なら0を戻す
if ( ( 0 >= a ) && ( 0 >= b ) ) return 0;
009 010
// 両方の値が同じならaを戻す
if ( a == b ) return a;
012 013 014
// 片方の値が0以下なら0を戻す if ( ( 0 >= a ) || ( 0 >= b ) ) return Math.max( a, b );
016 017 018 019 020 021 022 023 024
// 最大公約数を求めるループ int r = a % b; while ( 0 != r ) { a = b; b = r; r = a % b; } return b;
028 029 030 031 032 033 034 035 036 037 038 039 040 041 042 043 044 045 046 047 048 049 050 051 052 053 054 055 056 057 058
// メイン 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 ) ); } }
以上です。
公約数に関するコンテンツ
「公約数」に関係があるコンテンツをまとめています。
関連コンテンツ
広告
