C语言求最大公约数的方法介绍，达内C++的小编首先介绍下最大公约数的概念，然后再列举三种常见的求最大公约数的方法。

一、最大公约数的概念

最大公因数，也称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个。a，b的最大公约数记为(a，b)，同样的，a，b，c的最大公约数记为(a，b，c)，多个整数的最大公约数也有同样的记号。C语言求最大公约数有多种方法，常见的有质因数分解法、短除法、辗转相除法、更相减损法。

二、用C语言求最大公约数的三种方法

①辗转相除法求最大公约数

算法简介：“辗转相除法”也叫“欧几里得算法”

用辗转相除法求几个数的最大公约数，可以先求出其中任意两个数的最大公约数，再求这个最大公约数与第三个数的最大公约数，依次求下去，直到最后一个数为止。最后所得的那个最大公约数，就是所有这些数的最大公约数。

将两个数a，b相除，如果余数c不等于0，就把b的值给a，c的值给b，直到c等于0，此时最大公约数就是b

流程图：

C语言算法代码：

[cpp] view plain copy

//用来计算时间

inline unsigned __int64 GetCycleCount()

{

__asm

{

_emit 0x0F;

_emit 0x31;

}

}

//辗转相除法

void zhanzhuan()

{

int a = 0,b,c,m,n;

long starttime,endtime,alltime,freq;

unsigned long t1,t2;

LARGE_INTEGER num;

QueryPerformanceFrequency(&num);

freq = num.QuadPart;

printf("请输入所求的两个数字\n");

t1 = (unsigned long)GetCycleCount();//从这开始计时

scanf("%d%d",&a,&b);

m = a;

n = b;

while(c)//如果c等于0，那么最大公约数为b

{

c = a%b;//c是a除以b的余数

if(c)//如果c不等于0就把b的值给a，c的值给b

{

a = b;

b = c;

}

}

t2 = (unsigned long)GetCycleCount();

printf("%d和%d的最大公约数是:%d\n",m,n,b);

printf("所用时间:%f\n秒",(t2 - t1)*1.0/freq);

printf("\n");

<span style="color:#333333;"><span style="font-size:18px;">}</span></span>

②更相减损术求最大公约数

算法简介：“更相减损法”——出自《九章算术》

第一步：任意给定两个正整数;判断它们是否都是偶数。若是，则用2约简;若不是则执行第二步。

第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。

则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。

其中所说的“等数”，就是最大公约数。求“等数”的办法是“更相减损”法。所以更相减损法也叫等值算法。

将两个数中较大的数a减去较小的数b，如果差c等于0，那么最大公约数为b，如果不等于0，则将b的值给a，c的值给b，继续相减直到差等于0。

流程图：

C语言算法代码：

[cpp] view plain copy

inline unsigned __int64 GetCycleCount()

{

__asm

{

_emit 0x0F;

_emit 0x31;

}

}

void GXJS()

{

int a,b,c,m,n;

long starttime,endtime,alltime,freq;

unsigned long t1,t2;

LARGE_INTEGER num;

QueryPerformanceFrequency(&num);

freq = num.QuadPart;

printf("请输入所求的两个数\n");

scanf("%d%d",&a,&b);

t1 = (unsigned long)GetCycleCount();//从这开始计时

m = a;

n = b;

while(c)//如果差等于0，结束循环，最大公约数为b

{

if(a>b)//比较两个数的大小

c = a - b;

else

c = b -a;

if(c)//根据差是否等于0，进行值的交换

{

a = b;

b = c;

}

}

t2 = (unsigned long)GetCycleCount();

printf("%d和%d的最大公约数为:%d\n",m,n,b);

printf("所用时间:%f\n秒",(t2 - t1)*1.0/freq);

printf("\n");

<span style="font-size:18px;">}</span>

③穷举法求最大公约数

算法简介：将两个数a，b中较小的值赋给i，将a除以i，b也除以i，若两者的余数同时为0时，此时的i就是两者的最大公约数。若不等于0，则将i-1，继续将a除以i，b除以i，直至余数同时为0。

流程图：

C语言算法代码：

[cpp] view plain copy

//用来计算时间

inline unsigned __int64 GetCycleCount()

{

__asm

{

_emit 0x0F;

_emit 0x31;

}

}

void qiongju()

{

int a,b,c,i,m,n;

long starttime,endtime,alltime,freq;

unsigned long t1,t2;

LARGE_INTEGER num;

QueryPerformanceFrequency(&num);

freq = num.QuadPart;

printf("请输入所求的两个数\n");

scanf("%d%d",&a,&b);

m = a;

n = b;

if(a>b)//将较小的值赋给i

i = b;

else

i = a;

for(i;i>0;i--)

{

if(a%i == 0 && b%i == 0)//判断余数是否同时为0

break;//跳出循环

}

t2 = (unsigned long)GetCycleCount();

printf("%d和%d的最大公约数为%d\n",m,n,i);

printf("所用时间:%f\n秒",(t2 - t1)*1.0/freq);

printf("\n");

}

C语言求最大公约数小知识：“内存对齐”原则，每个变量对齐到对齐数的整数倍处[对齐数等于变量自身的大小和默认对齐数的较小值]。