Stein算法的正确性算法是计算两个数的传统算法

2、斯坦算法

欧几里得算法是计算两个数的最大公约数的传统算法。无论是理论上还是效率上都非常好。但他有一个致命的缺陷，只在大素数时才表现出来。

考虑到目前的硬件平台c语言公约数和公倍数，一般整数最多为64位。对于这样的整数，计算两个数之间的模非常简单。对于字长为 32 位的平台，计算两个不超过 32 位的整数的模只需要一个指令周期，而计算一个小于 64 位的整数的模只需要几个周期。然而，对于较大的素数，这样的计算过程必须由用户自己设计。为了计算两个超过 64 位的整数的模，用户可能不得不使用类似于手动多位数除法的试商方法。这个过程不仅复杂，而且消耗大量的CPU时间。对于现代密码算法，有很多情况需要计算128位以上的素数，这类程序的设计急于放弃除法和取模。

Stein 算法是 J. Stein 在 1961 年提出的。这种方法也是计算两个数的最大公约数。与欧几里得算法不同，Stein 算法只有整数移位和加减法c语言公约数和公倍数，这对程序员来说是一个福音。

为了说明Stein算法的正确性，我们首先要注意以下结论：

gcd(a,a) = a，即一个数和它自己的公约数就是它自己

gcd(ka,kb) = k gcd(a,b)，即最大公约数运算和乘法运算可以互换。特别是，当k=2时，表示两个偶数的最大公约数一定能被2整除

C++/java 实现

// c++/java stein算法

int gcd(int a,int b){

如果（ab{

int temp = a;

a = b;

b=温度；

}

if(0==b)//基本情况

返回一个；

if(a%2==0 && b%2 ==0)//a 和 b 是偶数

返回 2*gcd(a/2,b/2);

if ( a%2 == 0)//只有a是偶数

返回 gcd(a/2,b);

if ( b%2==0 )// 只有 b 是偶数

返回 gcd(a,b/2);

return gcd((a+b)/2,(a-b)/2);// a 和 b 是奇数

}

2.最小公倍数：

用最大公约数求最小公倍数

步骤：

一、求最大公约数

二、 最小公倍数是两个数除以最大公约数的乘积。