C语言辗转相除法求最大公约数_辗转相除法c++

​

大家好，我是架构君，一个会写代码吟诗的架构师。今天说一说C语言辗转相除法求最大公约数_辗转相除法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；明确逻辑后，代码就比较简单，只需要一个循环语句就可以实现。

今天文章到此就结束了，感谢您的阅读，Java架构师必看祝您升职加薪，年年好运。