首页 > 代码库 > 求m和n的最大公约数和最小公倍数

求m和n的最大公约数和最小公倍数

2024-09-07 14:19:29   221人阅读

题目：输入两个正整数m和n，求其最大公约数和最小公倍数。 

做这道题时,特意去查看了一下什么是最大公约数和最小公倍数.

后来直接去看了求解的思想,相信到企业中不会要求你闭门造车,若已有先例,可以研究之后拿来使用.

具体的思想是这样的:

　　1>使两个数,m大于n

　　2>m%n 若结果为0,那么n就是最大公约数

　　　　　　 若结果不为0,那么就要让n%(m%n).

写到这边就会发现,这又是一道关于递归的思想的问题.每次的运算都和上一次的运算的结果有关.

因此代码如下.

 1 //递归算法
 2     public static int maxCommonDivisor(int m, int n){
 3         if(m < n){
 4             int temp = m;
 5             m = n;
 6             n = temp;
 7         }
 8         if(m % n == 0){
 9             return n;
10         }else{
11             return maxCommonDivisor(n, m%n);
12         }
13         
14     }

 

 下面的这一种写法,和递归的思想实质上是一致的.采用了循环的形式.

 1     //循环法
 2     public static int maxCommonDivisor2(int m, int n){
 3         if(m < n){
 4             int temp = m;
 5             m = n;
 6             n = temp;
 7         }
 8         while(m % n != 0){
 9             int temp = m % n;
10             m = n;
11             n = temp;
12         }
13         return n;
14     }

 

最后,在求得最大公约数的基础上,最小公倍数很容易求得.

是m和n的乘积再除以最大公约数

1     public static int minCommonMultiple(int m, int n){
2         return m*n/maxCommonDivisor2(m, n);
3         
4     }

 

 

大神真的有很多,以上的代码写的很规范,包括命名(不是我起的),很专业.对于我的学习很有帮助.

求m和n的最大公约数和最小公倍数


联系
我们