- 暴力枚举法
public class test {
public static int genGreatestCommonDivisor(int a,int b){
int big = a>b ? a:b;
int small = a<b ?a:b;
if(big%small == 0){
return small;
}
for (int i = small/2; i >1; i++) {
if(small %i==0 && big%i==0){
return i;
}
}
return 1;
}
public static void main(String[] args) {
System.out.println(genGreatestCommonDivisor(25,5));
}
}
- 欧几里得算法
public class test {
public static int genGreatestCommonDivisor(int a,int b){
int big = a>b ? a:b;
int small = a<b ? a:b;
if(big%small == 0){
return small;
}
return genGreatestCommonDivisor(big%small,small);
}
public static void main(String[] args) {
System.out.println(genGreatestCommonDivisor(25,10));
}
}
- 更相减损术
public class test {
public static int genGreatestCommonDivisor(int a,int b){
if(a == b){
return a;
}
int big = a>b ? a:b;
int small = a<b ? a:b;
return genGreatestCommonDivisor(big - small,small);
}
public static void main(String[] args) {
System.out.println(genGreatestCommonDivisor(57,10));
}
}
