Java中使用辗转相除法求最大公约数

发布时间：2020-12-14 17:45:17 所属栏目：Java 来源：网络整理

导读：比较好用的是辗转相除法。比如：49和91 a b temp 49 % 91 = 49 91 % 49 = 42 49 % 42 = 7 42 % 7 = 0 所以最大公约数就是7. public class T { public static void main(String[] args) { int gcd = gcd(91,49); System.out.println(gcd); } /** * greatest

比较好用的是辗转相除法。
比如：49和91
a b temp
49 % 91 = 49
91 % 49 = 42
49 % 42 = 7
42 % 7 = 0
所以最大公约数就是7.

public class T {
 public static void main(String[] args) {
 int gcd = gcd(91,49);
 System.out.println(gcd);
 }

 /**
 * greatest commond divisor
 * @param a
 * @param b
 * @return
 */
 public static int gcd(int a,int b) {
 while(b != 0) {
  int temp = a%b;
  a = b;
  b = temp;
 }
 return a;
 }

}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!