黑马程序员技术交流社区

标题: 求最大公约数和最小公倍数 [打印本页]

---

作者: 夜写意    时间: 2015-7-18 11:05
标题: 求最大公约数和最小公倍数


简单的方法求结果，没有做优化，只是分享思路。

1. /*
   
2. * 需求：输入两个正整数m和n，求其最大公约数和最小公倍数。   
   
3. * 思路：1.定义一个方法，方法接收一个int类型的整数m，n
   
4. *                         从2~n找出m和n都能整除的数
   
5. *                         第一次找到后，重新调用此方法，传入m、n除以这个数的商
   
6. *                         把这个数加到数组中并跳出此循环
   
7. *                         返回此数组
   
8. *                 2.调用定义的方法，传入m和n。所得的数组为他们的公约数，最大值为最大公约数
   
9. *                 3.用m分别除以数组的每个元素，得的商再乘以n，得的值就是他们的最小公倍数。
   
10. * */
    
11. public class Test06 {
    
12.         public static void main(String[] args) {
    
13.                 new GetTest06(55,77);
    
14.         }
    
15. }
    
16. 
    
17. class GetTest06 {
    
18.         int[] arr = new int[20];
    
19.         int x = 0;
    
20.         int m, n;
    
21. 
    
22.         public GetTest06(int m, int n) {
    
23.                 super();
    
24.                 this.m = m;
    
25.                 this.n = n;
    
26.                 getNum(m, n);
    
27.                 getGongYueShu();
    
28.                 getGongBerShu();
    
29.                
    
30.         }
    
31. 
    
32.         public void getNum(int m, int n) {
    
33.                 for (int i = 2; i < m; i++) {
    
34.                         if (m % i == 0 && n % i == 0) {
    
35.                                 getNum(m / i, n / i);
    
36.                                 arr[x++] = i;
    
37.                                 break;
    
38.                         }
    
39.                 }
    
40.                 // return arr;
    
41.         }
    
42. 
    
43.         public void getGongYueShu() {
    
44.                 Arrays.sort(arr);
    
45.                 System.out.println("最大公约数：" + arr[arr.length-1]);
    
46. 
    
47.         }
    
48. 
    
49.         public void getGongBerShu() {
    
50.                 for (int i : arr) {
    
51.                         if (i != 0) {
    
52.                                 m /= i;
    
53.                         }
    
54.                 }
    
55.                 System.out.println("最小公倍数：" + m * n);
    
56.         }
    
57. 
    
58. }

复制代码

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2