程序c語言最小公倍數和最大公約數的簡單介紹

本文目錄一覽：

• 1、c語言求最大公約數和最小公倍數
• 2、c語言編程，求兩個數的最大公約數和最小公倍數
• 3、c語言如何求最大公約數和最小公倍數
• 4、最大公約數和最小公倍數c語言演算法
• 5、c語言如何求最小公倍數和最大公約數

c語言求最大公約數和最小公倍數

c語言求最大公約數和最小公倍數 求最小公倍數演算法： 最小公倍數=兩整數的乘積÷最大公約數 求最大公約數演算法： (1)輾轉相除法 有兩整數a和b：

① a%b得餘數c ② 若c=0，則b即為兩數的最大公約數 ③ 若c≠0，則a=b，b=c，再回去執行① 例如求27和15的最大公約數過程為： 27÷15 餘1215÷12餘312÷3餘0因此，3即為最大公約數

c語言編程，求兩個數的最大公約數和最小公倍數

這樣寫：

#include

void

main()

{

int

m,n,i,r,temp;

printf(“請輸入第一個數的值:

“);

scanf(“%d”,m);

printf(“請輸入第二個數的值:

“);

scanf(“%d”,n);

if(nm)

{

temp=m;

m=n;

n=temp;

}

i=n;

while(i%m!=0)

{

i=i+n;

}

printf(“最小公倍數是:%d

\n”,i);

r=m%n;

while(r!=0)

{

m=n;

n=r;

r=m%n;

}

printf(“最大公約數是:%d

\n”,n);

}

圖：

c語言如何求最大公約數和最小公倍數

#include stdio.h

int main()

{

int a,b,c,m,t;

printf(“請輸入兩個數:\n”);

scanf(“%d%d”,a,b);

if(ab)

{

t=a;

a=b;

b=t;

}

m=a*b;

c=a%b;

while(c!=0)

{

a=b;

b=c;

c=a%b;

}

printf(“最大公約數是:\n%d\n”,b);

printf(“最小公倍數是:\n%d\n”,m/b);

}

擴展資料

演算法思想

利用格式輸入語句將輸入的兩個數分別賦給 a 和 b，然後判斷 a 和 b 的關係，如果 a 小於 b，則利用中間變數 t 將其互換。

再利用輾轉相除法求出最大公約數，進而求出最小公倍數。最後用格式輸出語句將其輸出。

#includestdio.h是在程序編譯之前要處理的內容，稱為編譯預處理命令。編譯預處理命令還有很多，它們都以「#」開頭，並且不用分號結尾，所以是c語言的程序語句。

最大公約數和最小公倍數c語言演算法

最大公約數c語言編程的常用思路是：按照從大（兩個整數中較小的數）到小（到最小的整數1）的順序求出第一個能同時整除兩個整數的自然數，即為所求。

兩個數的最大公約數有可能是其中的小數，所以在按從大到小順序找尋最大公約數時，循環變數i的初值從小數n開始依次遞減，去尋找第一個能同時整除兩整數的自然數，並將其輸出。

需要注意的是，雖然判定條件是i0，但在找到第一個滿足條件的i值後，循環沒必要繼續下去，如，25和15，最大公約數是5，對於後面的4、3、2、1沒必要再去執行，但此時判定條件仍然成立，要結束循環只能藉助break語句。

具體代碼實現：

#includestdio.h

int main()

{

int m,n,temp,i;

printf(“Input mn:”);

scanf(“%d%d”,m,n);

if(mn)/*比較大小，使得m中存儲大數，n中存儲小數*/

{/*交換m和n的值*/

temp=m;

m=n;

n=temp;

}

for(i=n;i0;i–)/*按照從大到小的順序尋找滿足條件的自然數*/

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

{/*輸出滿足條件的自然數並結束循環*/

printf(“The GCD of%d and%d is:%d\n”,m,n,i);

break;

}

return 0;

}

c語言如何求最小公倍數和最大公約數

解題步驟：

1、求最大公約數

對兩個正整數a,b如果能在區間[a,0]或[b,0]內能找到一個整數temp能同時被a和b所整除，則temp即為最大公約數。

2、求最小公倍數

對兩個正整數a,b,如果若干個a之和或b之和能被b所整除或能被a所整除，則該和數即為所求的最小公倍數。

//窮舉法求兩數的最大公約數

int divisor(int a,int b)

{

int temp;//定義義整型變數

temp=(agt;b)?b:a;//採種條件運算表達式求出兩個數中的最小值

while(tempgt;0){

if(a%temp==0b%temp==0)//只要找到一個數能同時被a,b所整除，則中止循環

break;

temp–;//如不滿足if條件則變數自減，直到能被a,b所整除

}

return temp;//返回滿足條件的數到主調函數處

}

//窮舉法求兩數的最小公倍數

int multiple(int a,int b)

{

int p,q,temp;

p=(agt;b)?a:b;//求兩個數中的最大值

q=(agt;b)?b:a;//求兩個數中的最小值

temp=p;//最大值賦給p為變數自增作準備

while(1){//利用循環語句來求滿足條件的數值

if(p%q==0)

break;//只要找到變數的和數能被a或b所整除，則中止循環

p+=temp;//如果條件不滿足則變數自身相加

}

return p;

}

擴展資料：

用窮舉法解題時，就是按照某種方式列舉問題答案的過程。針對問題的數據類型而言，常用的列舉方法一有如下三種：

（1）順序列舉是指答案範圍內的各種情況很容易與自然數對應甚至就是自然數，可以按自然數的變化順序去列舉。

（2）排列列舉有時答案的數據形式是一組數的排列，列舉出所有答案所在範圍內的排列，為排列列舉。

（3）組合列舉當答案的數據形式為一些元素的組合時，往往需要用組合列舉。組合是無序的。

例子如下：在公元五世紀我國數學家張丘建在其《算經》一書中提出了「百雞問題」：

「雞翁一值錢5，雞母一值錢3，雞雛三值錢1。百錢買百雞，問雞翁、母、雛各幾何？」這個數學問題的數學方程可列出如下：

Cock+Hen+Chick=100

Cock*5+Hen*3+Chick/3=100

顯然這是個不定方程，適用於窮舉法求解。依次取Cock值域中的一個值，然後求其他兩個數，滿足條件就是解。

該問題的C語言程序演算法如下：

int Cock,Hen,Chick;/*定義公雞，母雞，雞雛三個變數*/

Cock=0;

while(Cocklt;=19)/*公雞最多不可能大於19*/

{Hen=0;

whlie(Henlt;=33)/*母雞最多不可能大於33*/

{Chick=100-Cock-Hen;

if(Cock*15+Hen*9+Chick==300)/*為了方便，將數量放大三倍比較*/

printf(“\n公雞=%d\n母雞=%d\n雛雞=%d”,Cock,Hen,Chick);

Hen=Hen+1;

}

Cock=Cock+1;

}

參考資料：

百度百科——窮舉法