丘凤光 发表于 2013-3-30 00:08
小程序标题:最大公因数公最小倍数
小程序题目:求两个数的最大公因数、求两个数的最小公倍数
小程序答案: ...
出题者楼层及时间:第77楼,时间为:2013年3月30日
答题者次数:我是本题的第1位答题者,上一个答题者楼层数为:无。
小程序题目:最大公因数公最小倍数
小程序思路:
1、最大公因数:用较小的数假作最大公因数去判断较大的数,不符合,较小数以此除2、3、4。。直到值为1
2、最小公倍数:两数积除以两数的最大公因数- public class Demo01 {
- public static int gcd(int m, int n) {
- // 最大公因数使用辗转相除法来求
- int min = m<=n?m:n; //获取两个数中较小的一个
- int max = min==m?n:m; //获取较大的一个
- for(int i = 1;i<=min;i++){
- if(min%i==0){
- int temp = min/i;//最大公因数从min开始,以此min/2,min/3...
- if(max%temp == 0){ //直到min/i后的值可以被max整除
- return temp;
- }
- }
- }
- return 1; //当然上面的return最终至少会返回1,这个执行不到,但为了程序不报错。
- }
- public static int lcm(int m, int n) {
- // 两个数的积除以两个数的最大公因数即为最小公倍数
- return m*n/gcd(m,n);
- }
- public static void main(String[] args) {
- System.out.println("(324, 42)的最大公因数为:" + gcd(324, 42));
- System.out.println("(324, 42)的最小公倍数为:" + lcm(324, 42));
- }
- }
复制代码 |