Skip to content

Instantly share code, notes, and snippets.

@chenyuxiang0425
Created August 21, 2020 13:24
Show Gist options
  • Select an option

  • Save chenyuxiang0425/e953f9a98cc6b9d58f4060458bc1a4ad to your computer and use it in GitHub Desktop.

Select an option

Save chenyuxiang0425/e953f9a98cc6b9d58f4060458bc1a4ad to your computer and use it in GitHub Desktop.
最大公约数 算法
/**
* 求两个非负整数的最大公约数
* @param p 非负整数
* @param q 非负整数
*/
public static int gcd(int p, int q) {
if (q == 0) return p;
int r = p % q;
return gcd(q,r);
}

这里的方法其实是每次的两个数

  • 大的数变为 -> 大的数 % 小的数的余数
  • 直到余数为 0 时,另一个数就是最小公约数

理解这个算法需要画图 -> 画一个长宽为p、q的矩形

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment