這里將介紹求兩個正整數的最小公倍數(Least Common Multiple，LCM)的方法。提供兩種主要思路，一種是直接根據最小公倍數的定義設計算法，一種是由最大公約數計算得出。下面來介紹這兩種方法。

定義法

求解兩個正整數的最小公倍數的第一種思路，根據定義設計算法，最小公倍數的本質是一個最小的能同時被兩整數整除的自然數。我們先比較兩數大小，從較大數開始向上遞增，直到找到那個最小公倍數。

代碼如下：

#include

int main()

{

int i=0;

int m,n,temp;

printf("請輸入兩個正整數:");

scanf("%d %d",&m,&n);

if( m

{

temp=n;

n=m;

m=temp;

}

for(i=m;i>0;i++) //從較大數開始尋找符合條件的最小公倍數

{

if( i%m==0&&i%n==0 )

{

printf("%d和%d的最小公倍數是%d",m,n,i);

break;

}

}

return 0;

}

輔助法

求最小公倍數也可以借助最大公約數輔助計算，公式為最小公倍數=兩數的乘積/最大公約(因)數。解題時避免將兩個問題混淆。

連續整除檢測法

這種方法的實現原理是，先取出兩個數中的較小數，賦值給temp(temporary)，接著用其中一個數與temp求余，若余數不為0，則temp-1，循環該步驟直到余數為0。再用另一個數，重復此步驟，最后得出的值利用公式計算得到這兩個數的最小公倍數。

代碼如下：

#include

int main()

{

int i=0;

int m,n,temp;

printf("請輸入兩個正整數:");

scanf("%d %d",&m,&n);

if( m>n )

{

temp=n;

}else //m=n在此不需要單獨討論

{

temp=m;

}

for(i=temp;i>0;i--) //如果從i=1開始，得出公約數也無法保證其為最大公約數。

{

if(m%i==0 && n%i==0)

break;

}

printf("%d和%d的最小公倍數是%d",m,n,m*n/i);

return 0;

}

歐幾里得算法

這種方法的實現原理是求兩個正整數的余數r(remainder)，再用兩個正整數中的較小數與其再求余直到余數為0時，此時的較小數就是最大公約數。最后利用公式計算得到這兩個數的最小公倍數。

代碼如下：

#include

int main()

{

int m,n,r;

printf("請輸入兩個正整數:");

scanf("%d %d",&m,&n);

int x=m*n; //x用于存放m與n的乘積

printf("%d%和%d的最小公倍數是",m,n); //此時輸出m和n的值還沒改變

r=m%n;

do //不用比較大小，若m小于n，則會在第一遍循環交換位置

{

m=n;

n=r;

r=m%n;

}while(r!=0);

printf("%d",x/n);

return 0;

}

相減法

這種方法比較易于理解，原理是先判斷兩個正整數大小，并將較大數與較小數的差值賦給較大數，循環此步驟直到兩數相等，此時得出最大公約數。最后利用公式計算得到這兩個數的最小公倍數。

代碼如下：

#include

int main()

{

int m,n;

printf("請輸入兩個正整數:");

scanf("%d %d",&m,&n);

int x=m*n; //x用于存放m與n的乘積

printf("%d%和%d的最小公倍數是",m,n);

do

{

if(m>n)

{

m=m-n;

}else

{

n=n-m;

}

}while(m!=n);

printf("%d",x/n);

return 0;

}

最后把這幾種方法構建為函數lcm并嘗試調用。

代碼如下：

#include

int lcm1(int m,int n)

{

int i=0;

int temp;

if( m

{

temp=n;

n=m;

m=temp;

}

for(i=m;i>0;i++) //從大數開始尋找符合條件最小公倍數

{

if( i%m==0&&i%n==0 )

{

break;

}

}

return i;

}

int lcm2(int m,int n)

{

int i=0;

int temp;

if( m>n )

{

temp=n;

}else //m=n在此不需要單獨討論

{

temp=m;

}

for(i=temp;i>0;i--) //如果從i=1開始，得出公約數也無法保證其為最大公約數。

{

if(m%i==0 && n%i==0)

break;

}

return i;

}

int lcm3(int m,int n)

{

int r=m%n;

do //不用比較大小，若m小于n，則會在第一遍循環交換位置

{

m=n;

n=r;

r=m%n;

}while(r!=0);

return n;

}

int lcm4(int m,int n)

{

do

{

if(m>n)

{

m=m-n;

}else

{

n=n-m;

}

}while(m!=n);

return n;

}

int main()

{

printf("請輸入兩個正整數: ");

int x,y;

scanf("%d %d",&x,&y);

int a=lcm1(x,y);

int b=lcm2(x,y);

int c=lcm3(x,y);

int d=lcm4(x,y);

printf("%d和%d的最小公倍數為%d\n",x,y,a);

printf("%d和%d的最小公倍數為%d\n",x,y,x*y/b);

printf("%d和%d的最小公倍數為%d\n",x,y,x*y/c);

printf("%d和%d的最小公倍數為%d",x,y,x*y/d);

return 0;

}

嘗試運行結果：

這篇文章涉及到了求解兩個正整數的最大公約數的三種方法，我在另一篇文章中有所介紹(文章鏈接如下)

求兩個正整數的最大公約數的三種方法

求解最大公約數與最小公倍數有很多相似的思路，理解好便可熟練應用。

總結

以上是生活随笔為你收集整理的c语言两个正整数的最小公倍数,C语言求两个正整数的最小公倍数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。