题目：输入两个正整数m 和n，求其最大公约数和最小公倍数。
程序分析：利用辗除法。
设两数为a、b(b<a)，求它们最大公约数(a、b)的步骤如下：
用b除a，得a=bq......r 1(0≤r)。
若r1=0，则(a，b)=b；若r1≠0，则再用r1除b，得b=r1q......r2 (0≤r2).
若r2=0，则(a，b)=r1，若r2≠0，则继续用r2除r1,……
如此下去，直到能整除为止。其最后一个非零余数即为(a，b)。

另外，最小公倍数等于两数之积除以最大公约数。

1. class Test06
   
2. {
   
3.         public static void main(String[] args)
   
4.         {
   
5.                 System.out.println(getLCM(30,20));
   
6.         }
   
7.         //求最大公约数
   
8.         public static int getGCD(int a,int b)
   
9.         {
   
10.                 //需确定两数的大小
    
11.                 int great=a,low=b;
    
12.                 if (a<b)
    
13.                 {
    
14.                         great = b;
    
15.                         low = a;
    
16.                         //System.out.println("great="+great+" ; low="+low);
    
17.                 }
    
18.                 //求余数
    
19.                 int r= -1;
    
20.                 while(r!=0)
    
21.                 {
    
22.                         r= great%low;
    
23.                         great = low;
    
24.                         low=r;
    
25.                         //System.out.println("great="+great+" ; low="+low+" ; r="+r);
    
26.                 }
    
27.                 return great;
    
28.         }
    
29.         public static int getGCD2(int a,int b)
    
30.         {
    
31.                 //用递归计算最大公约数
    
32.                 int great=a,low=b;
    
33.                 if (a<b)
    
34.                 {
    
35.                         great = b;
    
36.                         low = a;
    
37.                         System.out.println("great="+great+" ; low="+low);
    
38.                 }
    
39.                 if (low != 0)
    
40.                 {
    
41.                         return getGCD2(low,great%low);//递归时return的应该是递归方法的返回值，而不是其中的变量
    
42.                 }
    
43.                 else
    
44.                 {
    
45.                         return great;
    
46.                 }
    
47.         }
    
48.         //求最小公倍数。最小公倍数等于两数之积除以最大公约数。
    
49.         public static int getLCM(int a,int b)
    
50.         {
    
51.                 return a*b/getGCD(a,b);
    
52.         }
    
53. }
    

复制代码

题目：输入两个正整数m 和n，求其最大公约数和最小公倍数。
程序分析：利用辗除法。
设两数为a、b(b<a)，求它们最大公约数(a、b)的步骤如下：
用b除a，得a=bq......r 1(0≤r)。
若r1=0，则(a，b)=b；若r1≠0，则再用r1除b，得b=r1q......r2 (0≤r2).
若r2=0，则(a，b)=r1，若r2≠0，则继续用r2除r1,……
如此下去，直到能整除为止。其最后一个非零余数即为(a，b)。

另外，最小公倍数等于两数之积除以最大公约数。

1. class Test06
   
2. {
   
3.         public static void main(String[] args)
   
4.         {
   
5.                 System.out.println(getLCM(30,20));
   
6.         }
   
7.         //求最大公约数
   
8.         public static int getGCD(int a,int b)
   
9.         {
   
10.                 //需确定两数的大小
    
11.                 int great=a,low=b;
    
12.                 if (a<b)
    
13.                 {
    
14.                         great = b;
    
15.                         low = a;
    
16.                         //System.out.println("great="+great+" ; low="+low);
    
17.                 }
    
18.                 //求余数
    
19.                 int r= -1;
    
20.                 while(r!=0)
    
21.                 {
    
22.                         r= great%low;
    
23.                         great = low;
    
24.                         low=r;
    
25.                         //System.out.println("great="+great+" ; low="+low+" ; r="+r);
    
26.                 }
    
27.                 return great;
    
28.         }
    
29.         public static int getGCD2(int a,int b)
    
30.         {
    
31.                 //用递归计算最大公约数
    
32.                 int great=a,low=b;
    
33.                 if (a<b)
    
34.                 {
    
35.                         great = b;
    
36.                         low = a;
    
37.                         System.out.println("great="+great+" ; low="+low);
    
38.                 }
    
39.                 if (low != 0)
    
40.                 {
    
41.                         return getGCD2(low,great%low);//递归时return的应该是递归方法的返回值，而不是其中的变量
    
42.                 }
    
43.                 else
    
44.                 {
    
45.                         return great;
    
46.                 }
    
47.         }
    
48.         //求最小公倍数。最小公倍数等于两数之积除以最大公约数。
    
49.         public static int getLCM(int a,int b)
    
50.         {
    
51.                 return a*b/getGCD(a,b);
    
52.         }
    
53. }
    

复制代码