2つの数の最大公約数を求めます:Java、Scala
1331 ワード
転がり相除法
2つの数が大きい場合、転がり相殺法を採用するのが便利である.
小数で大数を除いて、もし整除することができるならば、小数は求めた最大公約数です.さもなくば余数でさっきの除数を除きます;このように、一つの除算が整除するまで、除算数としての数が求められる最大公約数である.
例えば、4453と5767の最大公約数を求める場合、以下のように除算することができる.
5767÷4453=1余1314
4453÷1314=3余511
1314÷511=2余292
511÷292=1余219
292÷219=1余73
219÷73=3
5767と4453の最大公約数は73であることが分かった.
転がり相除法の適用は比較的に広く、短除法よりずっとよく、任意の2つの数の最大公約数を求めることを保証することができる.
class ex1 { int gys1(int m, int n) //ループ実装 { int k,y; if(m int gys 2(int m,int n)/再帰実装 { int k,y; if(m public static void main(String[] args) { ex1 e1=new ex1(); System.out.println(e1.gys1(256,128)); ex1 e2=new ex1(); System.out.println(e1.gys2(256,128)); } }
scala実装:
2つの数が大きい場合、転がり相殺法を採用するのが便利である.
小数で大数を除いて、もし整除することができるならば、小数は求めた最大公約数です.さもなくば余数でさっきの除数を除きます;このように、一つの除算が整除するまで、除算数としての数が求められる最大公約数である.
例えば、4453と5767の最大公約数を求める場合、以下のように除算することができる.
5767÷4453=1余1314
4453÷1314=3余511
1314÷511=2余292
511÷292=1余219
292÷219=1余73
219÷73=3
5767と4453の最大公約数は73であることが分かった.
転がり相除法の適用は比較的に広く、短除法よりずっとよく、任意の2つの数の最大公約数を求めることを保証することができる.
class ex1 { int gys1(int m, int n) //ループ実装 { int k,y; if(m
scala実装:
private def gcd(a: Int , b: Int ): Int =
if (b == 0) a else gcd(b, a % b)