因式分解的问题相信大家并不陌生，

一般的求最大公约数函数可以这么写：

long max(long a, long b) {long ma,mi; if(a>b)ma=a,mi=b; else ma=b,mi=a;

for(s=mi;s>1;s--) if((mi%s==0)&&(ma%s==0))break;

return s;}

但这个算法的缺点在于如果两数的最大公约数很小但两个数都很大的时候效率不高；

如1111和2223这个算法要1111次循环后才能得到结果；

再看这个：

long max(long a,long b) {long i,ma,mi,c=0; if(a>b){ma=a;mi=b;} else {ma=b;mi=a;} i=mi; while(i) {i=ma%mi; if(i>(mi/2))i=mi-i; ma=mi; mi=i; c++;} printf("c1=%ld\n",c); return ma;}

这也是一个求最大公约数的算法；

它的思想是：

求A和B的最大公约数，假设A>B;

A/B表示成假分数的形式为N+X/B。

如果X不等于0

那A和B的最大公约数=B和X的最大公约数

如果X=0那这两个数的最大公约数就是B，

再看这个结论：X<B;X和B的最大公约数=（B-X）和X的最大公约数；

利用上面这些结论，可以写出跌代的算法，

大家可以看代码自己研究一下：

最坏情况循环只需要执行log2(B)次，效率可以大大提高。

PS：这个算法是我昨天为了优化一个程序想到的，拿出来给大家分享一下

[此贴子已经被作者于2004-10-07 18:52:20编辑过]

你看看我的

main() {int x,y,z; scanf("%d %d",&x,&y); if(x<y) {z=x; x=y; y=z; } while(y!=0) {z=x%y; x=y; y=z; } printf("%d",x); getch(); }

精神可贵

思想和我一样，但少了一个优化对于求N和N+1的公约数效果欠佳。

今天翻了一下书，发现这是“欧几里德辗转相除法”

说一下，尊重专利

[此贴子已经被作者于2004-10-08 08:28:19编辑过]

我不知道是什么法 我只知道别人都这么用

楼主的优化不错，顶

int gcd(int a,int b) /* （a>b），注意b=0*/ { return b?gcd( b,a%b):a;}