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実装:
private def gcd(a: Int , b: Int ):  Int = 
    if  (b == 0) a else gcd(b, a % b)