2020.03.23
数学
最大公約数 その2
最大公約数を求める方法は以下の通りです。
２つの自然数を割り切れる２以上の最小公約数を求め、その約数で自然数を割ります。この計算を２以上の最小公約数が無くなるまで繰り返し行います。この計算で得られた全ての約数を掛け合わせた数が最大公約数になります。
Javaソースコード
GCD_2.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 059 060 061 062 063 064 065 066 067 068 069 070 071 072 073 074 075 076 077 078 079 080 081 082 083 084
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 ) ); } }
コンパイル ソースコードが「ANSI」の場合
C:\talavax\javasample>javac -encoding sjis GCD_2.java
コンパイル ソースコードが「UTF-8」の場合
C:\talavax\javasample>javac GCD_2.java
実行
C:\talavax\javasample>java GCD_2
出力結果
8と12の最大公約数は、4 13と4の最大公約数は、1 144と32の最大公約数は、16 0と10の最大公約数は、10 0と0の最大公約数は、0
２つの値の両方が０の場合は０を戻します。
Javaソースコードの解説
ここからは、このソースコードを上から順番に解説していきます。
001
public class GCD_2 {
クラス名を、GCD_2としています。
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
// 最大公約数の初期値 int ans = 1;
019 020
// 最大公約数を求めるループ for ( ; ; ) {
021 022
// 片方の値が1以下ならループを抜ける
if ( ( 1 >= a ) || ( 1 >= b ) ) break;
024 025
// ２以上の１番小さい公約数を求める int cd = 1;
026 027
int min= Math.min( a, b ); for ( int i = 2; i <= min; i ++ ) {
028 029 030 031 032 033 034 035 036 037
if ( 0 == ( a % i ) ) {
// aはiで割り切れた
if ( 0 == ( b % i ) ) {
// bはiで割り切れた
// 最も小さい公約数
cd = i;
break;
}
}
}
039 040
// ２以上の公約数がなかったらループを抜ける
if ( 1 == cd ) break;
042 043
// 最大公約数を掛け合わせる
ans *= cd;
変数ansがcdに掛けています。
045 046 047
// ２つの自然数を約数で割る
a /= cd;
b /= cd;
050
return ans;
最後に、変数ansを戻しています。
054 055 056 057 058 059 060 061 062 063 064 065 066 067 068 069 070 071 072 073 074 075 076 077 078 079 080 081 082 083 084
// メイン 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 ) ); } }
以上です。
関連コンテンツ
割り算で「割り切れる」、「割り切れない」ってどういうこと？
広告
