2011級Java第1周（春）項目——一求兩個整數的最大公約數的程式

求兩個整數的最大公約數

在數學中人們常用“輾轉相除法”求兩個整數的最大公約數。

其思想是，設兩數為a、b(a>b），求a和b最大公約數(a，b）的步驟如下：用b除a，得a÷b=q......r1(0≤r1）。若r1=0，則（a，b)=b；若r1≠0，則再用r1除b，得b÷r1=q......r2 (0≤r2）.若r2=0，則（a，b)=r1，若r2≠0，則繼續用r2除r1，……如此下去，直到能整除為止。其最後一個非零除數即為（a，b）。

Java源代碼實作：

[java]  view plain copy

1. package algorithms;  
2. import java.util.Scanner;  
3. public class gcd {  
4.     public static void main(String args[]){  
5.         int a,b,c = 0,r,max,min;  
6.         System.out.println("請輸入兩個數：");  
7.         Scanner x=new Scanner(System.in);  
8.         a=x.nextInt();  
9.         Scanner y=new Scanner(System.in);  
10.         b=y.nextInt();  
11.         if(a<=0||b<=0){  
12.             System.out.print("請確定輸入的數字大于等于零！");  
13.         }  
14.         else{  
15.             max = Math.max(a,b);  
16.             min = Math.min(a, b);  
17.             r = max%min;  
18.             while(r!=0){  
19.                 c=r;  
20.                 r = max%r;  
21.             }  
22.             System.out.println(a+"和"+b+"的最大公約數為："+c);  
23.             }  
24.         }  
25. }  

運作結果：