求最大公约数的快速算法

 
/**/ /*
 stein 算法求最大公约数，和欧基里德算法相比，效果更好:
 主要思想如下： 化归思想
 
  
 1.m为奇数时:
    (1)n也为奇数：gcd(m,n) = gcd((m+n)/2,(m-n)/2) ;
    (2)n为偶数：  gcd(m,n) = gcd(m,n/2) ;
  
 2.m为偶数时：
   (1) n也为偶数:gcd(m,n) = gcd(m/2,n/2);
   (2) n为奇数:  gcd(m,n) = gcd(m/2,n);

 3.m == n 时,gcd(m,n) = m 退出
  
*/
 
#include  < stdio.h >

int  stein_gcd (  int  m ,  int  n )
... {
    int temp,total=0 ;
    if ( m < n )
    ...{
         temp = m ;
         m = n ;
         n = temp ;
    }
    
    if ( n == 0 )
    return 0 ;
    
    while ( m != n )
    ...{
          if ( m & 1) /**//* 如果m 为奇数, 因为奇数的后面总有一个1,所以可以通过与1且一下来判断是否是偶数*/
          ...{
               if ( n & 1) /**//* m,n都为奇数*/
               ...{
                    temp = m ;
                    m = (m+n)>>1 ;
                    n = (temp-n)>>1;
               }
               else
               ...{
                    n  >>= 1 ;
               }
          }
          else /**//* m为偶数 */
          ...{
               if ( n & 1) /**//*n 为奇数*/
               ...{
                    m >>= 1 ; /**//*由于在这个过程中，m可能小于n ,所以要判断一下*/
                    if ( m < n )
                    ...{
                         temp = m ;
                         m = n ;
                         n = temp ;
                    }
               }
               else
               ...{
                    m >>= 1 ;
                    n >>= 1 ;
                    total ++ ; /**//*记录缩小的倍数*/
               }
          }
    }
    
    m <<= total ; /**//*还原大小*/
    
    return m ;
}

               
               
               
    
    
int  main( void )
... {
    int m,n,max=0;
    
    scanf("%d %d",&m,&n);
    
    max = stein_gcd(m,n);
    
    printf("max= %d ",max);
    
    
    /**//*
    test
    
    while( (scanf("%d",&m)) && m != 0 )
    {
           if ( m & 1)
           printf("%d是奇数 ",m);
           else
           printf("%d是偶数 ",m);
    }
    */       
    system("pause");
    return 0 ;
}