啦啦啦

又来写bug了

今日闲来无事

写写bug吧

求两个数的最大公约数

这样的问题 

对于知识渊博的giao giao来说

洒洒水啦

先来个传说中的

辗转相除法

话说公元前300年前一个叫欧几里得的人

吃了一颗冬枣

灵光一现

写出了这个算法

目的是求出两个正整数的最大公约数。

它是已知的最古老的算法

啧啧啧 

古色古香的算法啊

这条算法基于一个定理：两个正整数a和b（a>b），它们的最大公约数等于a除以b的余数c和b之间的最大公约数。比如10和25，25除以10商2余5,那么10和25的最大公约数，等同于10和5的最大公约数。

在两个数中，找出大数，用大数除以小数，得到整数商和余数，然后再不断地用除数（原来的小数）除以余数，直到没有余数为止。

那么除数即为最大公约数。

所以我们可以用一个循环来进行被除数、除数和余数之间的位置互换。

也可以用goto语句来进行循环操作。（goto语句在一个程序当中最好不要多次出现，否则程序很有可能混乱）

代码：

下图为运行结果

 

再来一个中国古代的算法

九章算术

牛b不？

这个算法出自于九章算术

更相减损法

更相减损法原本是为了约分而设计的：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。

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

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

则第一步中约掉的2的个数

与第二步减数和差相等的那个数是所求的最大公约数。

代码如下：

是不是很厉害？
想研究一下stein算法

先来大概以我的理解讲一下这个stein算法

1、如果ab都是偶数，记录下公约数2，同时除以2（右移一位）

2、其中一个为偶数，偶数除2（证明公约数不为2）

3、若均为奇数 a=|a-b| b=min(a,b) 

讲一下为什么要有这个算法

欧几里德算法（前面的那个算法）是计算两个数最大公约数的传统算法，他无论从理论还是从效率上都是很好的。

但是他有一个致命的缺陷，这个缺陷只有在大素数时才会显现出来。

听到了么？？

致命缺陷

我写的代码是最完美的

怎么可以有缺陷？
考虑现在的硬件平台，一般整数最多也就是64位，对于这样的整数，计算两个数之间的模是很简单的。对于字长为32位的平台，计算两个不超过32位的整数的模，只需要一个指令周期，而计算64位以下的整数模，也不过几个周期而已。但是对于更大的素数，这样的计算过程就不得不由用户来设计，为了计算两个超过64位的整数的模，用户也许不得不采用类似于多位数除法手算过程中的试商法，这个过程不但复杂，而且消耗了很多CPU时间。对于现代密码算法，要求计算128位以上的素数的情况比比皆是，设计这样的程序迫切希望能够抛弃除法和取模。
Stein算法由J. Stein 1961年提出。和欧几里德算法 算法不同的是，Stein算法只有整数的移位和加减法，这对于程序设计者是一个福音。
 

gcd(a,a) = a，也就是一个数和他自身的公约数是其自身
gcd(ka,kb) = k gcd(a,b)，也就是最大公约数运算和倍乘运算可以交换，特殊的，当k=2时，说明两个偶数的最大公约数必然能被2整除

// c++stein 算法
int gcd(int a,int b){
    if(ab{
        int temp = a;
        a = b;
        b=temp;
    }
    if(0==b)//the base case
        return a;
    if(a%2==0 && b%2 ==0)//a and b are even
        return 2*gcd(a/2,b/2);
    if ( a%2 == 0)// only a is even
        return gcd(a/2,b);
    if ( b%2==0 )// only b is even
        return gcd(a,b/2);

    return gcd((a+b)/2,(a-b)/2);// a and b are odd
 

}

 

就说这么多 

今天朕累了

休息啊