C语言——辗转相除法求最大公约数

一、题目分析

求12和18的最大公约数，一般我们会想到从1开始一直到12除1，18除1，然后再一起除2....直到找出都能除到的最大公约数，但是这样12和18我们至少要运行12次，一旦数字多了我们运行的内存和时间都会变大

所以我们可以使用辗转相除法

我们令a=12 b=18,t=a%b

用t=12%18=12,令a=b=18,b=t=12;

t=18%12=6,令a=b=12,b=t=6;

t=12%6=0,a=b=6,b=t=0

当b=0时，a为最大公约数

二、代码如下

#include <stdio.h>

int main()
{    
  int a,b,t;
  scanf("%d %d",&a,&b);
  while(b!=0){
  	t=a%b;
	a=b;
	b=t; 
  } 
  printf("%d",a);
}
 

总结：

辗转相除法，要明确终止条件，通过a和b取余，用t储存余数，再进行挪位，直到b=0，

就有最大公约数a；明确逻辑后，代码就比较简单，只需要一个循环语句就可以实现。