辗转相除法:
package com.qiqi.test;
import java.util.Scanner;
/*
* 输入两个正整数m和n,求其最大公约数和最小公倍数
* 辗转相除法:
* 1.用大数m/小数n得第一个余数
* 2.余数为0则n为最大公约数
* 3.余数不为0则把n的值给m,余数的值给n
* 4.再次相除直到余数为0,此时除数是最大公约数
* 5.最小公倍数=m*n/最大公约数
*/
public class Test10 {
public static void main(String[] args) {
Scanner cin=new Scanner(System.in);
int m,n,t;
System.out.println("请输入两个正整数:");
m=cin.nextInt();
n=cin.nextInt();
if(m<n) {
t=m;m=n;n=t;
}
t=gong(m,n);
System.out.println("最大公约数是"+t);
System.out.println("最小公倍数是"+m*n/t);
cin.close();
}
public static int gong(int a,int b) {
int k;
while((a%b)!=0) {
k=a%b;
a=b;
b=k;
}
return b;
}
}
枚举法:
package com.qiqi.test;
import java.util.Scanner;
/*
* 枚举法:
* 从两数中小数开始列举约数,找到公约数则停止列举,得到的就是最大公约数
* 最小公倍数:两数乘积/最大公约数
*/
public class Test11 {
public static int meiju(int a,int b) {
int p,q,k;
k=(a>b)?a:b;//较小的数
while(k>0) {
if(a%k==0&&b%k==0)
break;
k--;//不满足if条件则减1,直到能被a,b整除
}
return k;//最大公约数
}
public static void main(String[] args) {
Scanner cin=new Scanner(System.in);
int m,n,t;
System.out.println("请输入两个正整数:");
m=cin.nextInt();
n=cin.nextInt();
t=meiju(m,n);
System.out.println("最大公约数是"+t);
System.out.println("最小公倍数是"+m*n/t);
cin.close();
}
}