锐客网

  1. 首页 > it技术 > >

算法|Java 求两个整数中的最大公约数

辗转相除法（欧几里得算法）点击打开链接
对要求最大公因数的两个数a、b;
设b 若r1=0，则（a，b)=b；若r1≠0，则再用r1除b，得b=r1q+r2 (0≤r2 若r2=0，则（a，b)=r1，若r2≠0，则继续用r2除r1……如此循环，直到能整除为止。其最后一个非零余数即为（a，b）。
【算法|Java 求两个整数中的最大公约数】结论: 设两数为a、b(b

package com.itheima.basic; import java.util.Scanner; //导入包public class Test { public static void main(String[] args) { Scanner sc = new Scanner(System.in); //创建对象 System.out.println("请输入第一个整数"); int m = sc.nextInt(); //接受第一个数据 System.out.println("请输入第二个整数"); int n = sc.nextInt(); //接受第二个数据 int c = gcd(m, n); //调用方法，并返回最大公约数 System.out.println(m+"和"+n+"的最大公约数为:"+c); } public static int gcd(int m, int n) { if (n == 0) { return m; } int r = m % n; return gcd(n, r); }}


    推荐阅读


    上一篇：广东工业大学新生赛决赛H题

    下一篇：创意大爆炸|创意大爆炸|广告界59张系列新年海报