网站在线客服 源码苏州seo网络推广

一、最大公约数

   最大公因数，也称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个。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");
}

②更相减损术

算法简介：将两个数中较大的数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;elsec = 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");
}

//用来计算时间
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)//将较小的值赋给ii = b;elsei = a;for(i;i>0;i--){if(a%i == 0 && b%i == 0)//判断余数是否同时为0break;//跳出循环}t2 = (unsigned long)GetCycleCount(); printf("%d和%d的最大公约数为%d\n",m,n,i);printf("所用时间:%f\n秒",(t2 - t1)*1.0/freq); printf("\n");
}