欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

最大公约数和最小公倍数

程序员文章站 2022-05-28 20:06:34
最大公约数和最小公倍数 [cpp] //辗转相除法求最大公约数   int  gcd(int m,int n)  { ...
最大公约数和最小公倍数
[cpp]
//辗转相除法求最大公约数  
int  gcd(int m,int n) 

         int tem; 
         if(m<n){tem=m;m=n;n=tem;} 
         while(n!=0){ 
             tem=m%n; 
             m=n; 
             n=tem; 
             } 
            return m;                     

//辗转相减法求最大公约数  
int  gcd(int m,int n) 

         int tem; 
         while(n!=0){ 
             if(m<n){tem=m;m=n;n=tem;} 
             tem=m-n; 
             m=n; 
             n=tem; 
             } 
            return m;                     

//最小共倍数等于m*n/最大公约数,所以求出了最大公约数就能很快得出最小公倍数啦  
int lcm(int m,int n) 

  return m*n/gcd(m,n); 
}   

摘自  菜鸟的高手情节