a738: 最大公约数

內容 ：

小海豚要上初中了，也會了一點程序設計。海豚爸爸想起大約30年前上高一的時候自己第一次摸電腦。現在難以想像一下那種心情，那時候一個中國大陸一個大學畢業生（很稀罕的哦）月工資只有60元RMB，而一台蘋果II要6000元RMB。海豚爸爸有生以來輸入電腦的第一個程序，就是“最大公約數”。

輸入說明 ： 

每行2個數a, b 0 < a, b < 1000000000
EOF結束

輸出說明 ： 

對每對a,b 輸出其最大公約數

範例輸入 ： 

30 24
2 4

範例輸出:

6
2

提示： 

“輾轉相除法”，又稱“歐幾里德算法”。比如計算 30 和24 的最大公約數：
 30除以24，餘6 --> 24除以6，餘0 --> 得到最大公約數就是 6

標籤:

GCD

import java.util.Scanner;

public class a738 {

public static void main(String[] args) {

Scanner sc=new Scanner(System.in);

while(sc.hasNext()){

long a=sc.nextInt(),b=sc.nextInt();

if(a<b){

long c=a;

a=b;

b=c;

}

System.out.println(GCD(a,b));

}

}

static public long GCD(long a,long b){

if(b==0)

return a;

else

return GCD(b,a%b);

}

}