转自http://www.programfan.com/club/showbbs.asp?id=227318&page=1 bpttc的发言   int GCD_Stein( int x, int y ){        int factor = 0;        int temp;        if ( x < y )        {                temp = x;                x = y;                y = temp;        }        while ( x != y )        {                if ( x & 0x1 )                {/* when x is odd */                        if ( y & 0x1 )                        {/* when x and y are both odd */                                y = ( x - y ) >> 1;                                x -= y;                        }                        else                        {/* when x is odd and y is even */                                y >>= 1;                        }                }                else                {/* when x is even */                        if ( y & 0x1 )                        {/* when x is even and y is odd */                                x >>= 1;                                if ( x < y )                                {                                        temp = x;                                        x = y;                                        y = temp;                                }                        }                        else                        {/* when x and y are both even */                                x >>= 1;                                y >>= 1;                                ++factor;                        }                }        }        return ( x << factor );}Stein算法对两个正整数 x>y ：1.均为偶数 gcd(x,y)=2gcd(x/2,y/2)；2.均为奇数 gcd(x,y)=gcd((x+y)/2,(x-y)/2)；2.x奇y偶   gcd(x,y)=gcd(x,y/2)；3.x偶y奇   gcd(x,y)=gcd(x/2,y) 或 gcd(x,y)=gcd(y,x/2)；（注意此时判断 x/2和y的大小）

评论