1辗转相除
a对b取余，b赋值给a，余数赋值给b，直到b==0
public class GreatestCommon { public static void main(String[] args) { Scanner input = new Scanner(System.in); System.out.println("请输入第一个数："); int a = input.nextInt(); System.out.println("请输入第二个数："); int b = input.nextInt(); int j = 1; do { j = a % b; a = b; b = j; }while(b != 0); System.out.println("最大公约数是：" + a); } }
2枚举：
public class GreatestCommon { public static void main(String[] args) { Scanner imput = new Scanner(System.in); System.out.println("请输入第一个数字："); int num1 = imput.nextInt(); System.out.println("请输入第二个数字："); int num2 = imput.nextInt(); int k = 1; //存储最大公约数 int gcd = 1; //while循环找最大公约数 while(k <= num1 && k <= num2)//约数肯定比输入的数小 { if (num1 % k ==0 && num2 % k ==0)//找出公约数 { gcd = k; } k++; } System.out.println("数字" + num1 +"和数字" + num2 + "的最大公约数为" + gcd); } }
3：更相减损数
a,b两个数，大数减小数（重复操作）；直到相等数
public class GreatestCommon { public static void main(String[] args) { Scanner input = new Scanner(System.in); System.out.println("请输入第一个数："); int a = input.nextInt(); System.out.println("请输入第二个数："); int b = input.nextInt(); int j = 1; do { a = (a > b ? a - b : a); b = (a < b ? b - a : b); }while(a != b); System.out.println("最大公约数是：" + a); } }
