一、最大公约数
最大公因数，也称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个。a，b的最大公约数记为（a，b），同样的，a，b，c的最大公约数记为（a，b，c），多个整数的最大公约数也有同样的记号。
二、求最大公约数的三种方法
①辗转相除法
算法简介：将两个数a，b相除，如果余数c不等于0，就把b的值给a，c的值给b，直到c等于0，此时最大公约数就是b
流程图：
算法代码：
-
//用来计算时间
-
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>
②更相减损术
算法简介：将两个数中较大的数a减去较小的数b，如果差c等于0，那么最大公约数为b，如果不等于0，则将b的值给a，c的值给b，继续相减直到差等于0。
流程图：
算法代码：
-
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。
流程图：
算法代码：
-
//用来计算时间
-
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");
-
}
-
