题目:
输入两个正整数m和n (m>n),求其最大公约数和最小公倍数
代码:
这题目用小学里面学过的”辗转相除法“就可以求最大公约数了,而最小公倍数则是2个数乘积除以最大公约数。适当考虑下2个数大小就可以了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
|
package
com.charles.algo;
/**
* @author charles.wang
* 题目:输入两个正整数m和n (m>n),求其最大公约数和最小公倍数
*/
public
class
GongYueShuGongBeiShu {
private
GongYueShuGongBeiShu(){}
/**
* 用辗转相除法来计算最大公约数
*/
public
static
int
maxGongYue(
int
m,
int
n){
//确保m>=n 才可以做除法运算,否则交换2个数
int
temp;
if
(m<n){
temp= n;
n=m;
m=temp;
}
//计算余数,它会小于n
int
remain = m % n;
//如果整除了,那么除数就是最大公约数
if
(remain==
0
)
return
n;
//否则,递归调用
return
maxGongYue( n,remain);
}
/**
* 最小公倍数的值为二个数的乘积除以最大公约数
*/
public
static
int
minGongBei(
int
m,
int
n){
return
m*n/maxGongYue(m,n);
}
/**
* @param args
*/
public
static
void
main(String[] args) {
int
m =
12
;
int
n =
18
;
System.out.println(
"输入数为:"
+m+
" ,"
+n);
System.out.println(
"最大公约数为:"
+maxGongYue(m,n));
System.out.println(
"最小公倍数为:"
+minGongBei(m,n));
}
}
|
本文转自 charles_wang888 51CTO博客,原文链接:http://blog.51cto.com/supercharles888/1345651,如需转载请自行联系原作者