算法-求最大公约数和最小公倍数(Java)
- 最大公约数和最小公倍数
求最大公约数可以用三个方法来实现：辗转相除法，辗转相减法，穷举法。
求最小公倍数可以用一个公式来实现：xy=最大公约数最小公倍数。也可以用穷举法来实现。
- 求最大公约数
- 辗转相除法
public int max(int m,int n){
if(n==0){
return m;
}
int r=m%n;
return max(n,r);
}
- 辗转相减法
//辗转相减法
public static int max2(int m ,int n){
if(m==n) {
return m;
}else if(m>n){
return max(m-n,n);
}else {
return max(m ,n-m);
}
}
- 穷举法
int max = m>n?m:n;
int min = m<n?m:n;
for(int i=min;i>=1;i--){
if(max%i==0&&min%i==0){
System.out.println("最大公约数："+i);
break;
}
}
- 公式法
int temp = x * y /max(x,y);
- 穷举法
for(int i=max;i<=max*min;i++){
if(i%max==0&&i%min==0){
System.out.println("最小公倍数为："+i);
}
}
