求最大公约数的4种算法
for(z=0; z<10000000; z++) 循环只是为了增加程序的运行时间，让我们体会算法的时间复杂度。算法一：短除法
想法，采用短除法找出2个数的所有公约数，将这些公因子相乘，结果就是2个数的最大公约数。【找公因子，只能使用蛮力法】
#include<stdio.h>
#include<time.h>
void main()
{
int m=28,n=72;
int i,f=1;
int z;
clock_t start,finish;
double duration;
start= clock();
for(z=0; z<10000000; z++)
{
for(i=2;i<=m&&i<=n;)
{
while(m%i==0&&n%i==0)
{
f*=i;
m/=i;
n/=i;
}
i++;
}
}
finish=clock();
duration=(double)(finish-start)/CLOCKS_PER_SEC;
printf("time=%lf seconds\n",duration);
printf("result=%d\n",f);
}
image.png
算法二：辗转相除法
辗转相除法， 又名欧几里德算法（Euclidean algorithm），是求最大公约数的一种方法。它的具体做法是：用较小数除较大数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。
#include<stdio.h>
#include<time.h>
void main()
{
int m=28,n=72;
int i,f=1;
int z;
clock_t start,finish;
double duration;
start= clock();
for(z=0; z<10000000; z++)
{
if(m<n)
{
i=m;
m=n;
n=i;
}
i=m%n;
while(i)
{
m=n;
n=i;
i=m%n;
}
f=n;
}
finish=clock();
duration=(double)(finish-start)/CLOCKS_PER_SEC;
printf("time=%lf seconds\n",duration);
printf("result=%d\n",f);
}time=0.037000 seconds
result=4
Press any key to continue算法三：蛮力法，从2个公约数中较小的数开始递减，二个公约数除以它，可以同时除尽，变是最大公约数，我想的，很笨的一种。
#include<stdio.h>
#include<time.h>
void main()
{
int m=28,n=72;
int i,f=1;
int z;
clock_t start,finish;
double duration;
start= clock();
for(z=0; z<10000000; z++)
{
f=m>n?n:m;
for(i=f;i>0;i--)
{
if(m%i==0&&n%i==0)
{
f=i;
break;
}
}
}
finish=clock();
duration=(double)(finish-start)/CLOCKS_PER_SEC;
printf("time=%lf seconds\n",duration);
printf("result=%d\n",f);
}time=0.992000 seconds
result=4
Press any key to continue算法四：辗转相减法
辗转相减法是一种简便的求出两数最大公约数的方法。（更相减损术）辗转相减法（求最大公约数），即尼考曼彻斯法，其特色是做一系列减法，从而求得最大公约数。例如 ：两个自然数35和14，用大数减去小数，(35,14)->(21,14)->(7,14)，此时，7小于14，要做一次交换，把14作为被减数，即(14,7)->(7,7)，再做一次相减，结果为0，这样也就求出了最大公约数7
#include<stdio.h>
#include<time.h>
void exchange(int *m,int *n);
void main()
{
int m=28,n=72;
int i,f=1;
int z;
clock_t start,finish;
double duration;
start= clock();
if(m<n)
exchange(&m,&n);
for(z=0; z<10000000; z++)
{
i=m-n;
while(i)
{
if(i>n)
{
m=i;
}else
{
m=n;
n=i;
}
i=m-n;
}
f=m;
}
finish=clock();
duration=(double)(finish-start)/CLOCKS_PER_SEC;
printf("time=%lf seconds\n",duration);
printf("result=%d\n",f);
}
void exchange(int *m,int *n)
{
int temp;
temp=*m;
*m=*n;
*n=temp;
}time=0.020000 seconds
result=4
Press any key to continue看看4个算法的运行时间，还是我自己想的算法时间最久，来一个 大神拯救我吧。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018.03.12 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录