Question

设计一个算法，求840与1764的最大公因数

Answer 1

一楼的回答好像有点坑爹哦。。他那个是最笨的暴力方法。暴力去找对于高手，有更好的方法也就是数论当中的欧几里得算法欧几里得证明过a和b的最大公约数，等于b和a%b的最大公约数 %符号是取余的意思那么我们就可以设计一个不断递归的算法。把复杂度降到很低（几乎是一个常数级O（1）） 那么我来书写一下这个程序吧。#include<stdio.h> int Euclid(int a,int b){ if(b==0) return a; else return Euclid(b,a%b);} int main(){ int a,b; scanf("%d%d",&a,&b); printf("%d\n",Euclid(a,b)); return 0;} 运行结果：