最小公倍數c語言演算法

⑴ 最小公倍數怎麼求演算法c語言

求兩個正整數的最小公倍數，可以有很多種不同的計算方法。其中下面是一種用C語言實現的計算方法。
int gcd(int a,int b)
{int r;
while(b)
r=a%b,a=b,b=r;
return a;
}

⑵ c語言輸入三個數求最小公倍數演算法

先求兩個的最小公倍數，再求這個最小公倍數與第三個數的最小公倍數

#include<stdio.h>
intgcd(inta,intb)
{
return!b?a:gcd(b,a%b);
}
intlcm(inta,intb)
{
returna/gcd(a,b)*b;
}
intmain()
{
inta,b,c;
scanf("%d%d%d",&a,&b,&c);
printf("%d
",lcm(lcm(a,b),c));
return0;
}

⑶ 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=(a>b)?b:a;//采種條件運算表達式求出兩個數中的最小值

while(temp>0){

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

break;

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

}

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

}

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

int multiple(int a,int b)

{

int p,q,temp;

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

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

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

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

if(p%q==0)

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

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

}

return p;

}

(3)最小公倍數c語言演算法擴展閱讀：

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

（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(Cock<=19)/*公雞最多不可能大於19*/

{Hen=0;

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

{Chick=100-Cock-Hen;

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

printf(" 公雞=%d 母雞=%d 雛雞=%d",Cock,Hen,Chick);

Hen=Hen+1;

}

Cock=Cock+1;

}

⑷ 用C語言編寫程序求兩個數的最小公倍數,並輸出

如圖使用輾轉相除法求最小公倍數：

(4)最小公倍數c語言演算法擴展閱讀：

輾轉相除法， 又名歐幾里德演算法（Euclidean algorithm），是求最大公約數的一種方法。

它的具體做法是：用較大數除以較小數，再用出現的余數（第一餘數）去除除數，再用出現的余數（第二餘數）去除第一餘數，如此反復，直到最後余數是0為止。如果是求兩個數的最大公約數，那麼最後的除數就是這兩個數的最大公約數。

兩個數的最大公約數是指能同時整除它們的最大正整數。

設兩數為a、b（a2b），求a和b最大公約數（a，b）的步驟如下：

（1）用a除以b（a2b），得a÷b=q..n（0≤n）。

（2）若rn=0，則（a，b）=b；

（3）若r10，則再用b除以n，得b÷n=q..2（0sr2）

（4）若r2=0，則（a，b）=rn；若r20，則繼續用r1除以r2，.…，如此下去，直到能整除為止。

其最後一個余數為0的除數即為（a，b）的最大公約數。

⑸ C語言中，求兩個數的最小公倍數，的「高效」演算法是

這思路我自己想的，但是我也說不太明白，反正我知道怎麼回事
1先判斷大數%小數是不是0，是0那麼大數就是最小公倍數
2不是的話，讓大數%小數得到一個數，讓小數%得到的數，如果得0
那麼讓大數*（小數/(大數%小數)）,得到得數是最小公倍數
3如果2中小數%得到的這個數不等於0，那麼恭喜你，這兩個數的最小公倍數就是：大數*小數
4如果這兩個數相等，那麼，隨便一個都是最小公倍數
純手打，今天剛好做這個題，看到網上沒什麼答案，我就寫寫我的思路
C++語法如下：
int pd(int A,int B);
int main() {int i, k;goto C;
C: {
printf("第一個數："); scanf("%d", &i);
printf("第二個數："); scanf("%d", &k);
printf("這兩個數的公倍數為：%d\n\n", pd(i, k));
goto C; }
return 0;
}
int pd(int A, int B) {
int P;
if (A > B) {
if (A%B == 0) { P = A; }
else if (B % (A%B) == 0) { P = A*(B / (A%B)); }
else { P = A*B; }
}
else if (B > A) {
if (B%A == 0) { P = B; }
else if (A % (B%A) == 0) { P = B*(A / (B%A)); }
else { P = B*A; }
}
else { P = A; }
return P;
}

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

#include <stdio.h>

int gcd(int x ,int y)

{ int r;

for(;r=x%y;)x=y,y=r;

return y;

}

int main()

{ int a,b,c;

scanf("%d%d",&a,&b);

c=gcd(a,b);

printf("%d %d ",c,a*b/c);

return 0;

}

⑺ C語言求n個數的最小公倍數

你輸入的n是1吧，當你輸入1時，程序運行到for語句時，i的初值為1，由於條件判斷語句1<1不滿足，所以for語句根本就沒有執行。你精心設計最大公約數函數不僅沒有執行，甚至y也沒有被賦值。程序直接轉到printf語句。直接輸出的就是x，也就是你說的輸入的第一個數。由於程序使用了while語句，所以該程序不會自行結束。仍會等待你重新輸入n進行下一輪計算。

解決方法：在for語句i初始值由1改為0，即i=0,或程序運行時，n值你直接輸入2，但for循環只執行一次，然後依次輸入x，y的值。ps:其實你的程序，運行沒有錯，演算法設計的不是很好。我是把i改成0了。運行結果如圖。

⑻ C語言編程中最小公倍數怎麼求

思想：輸入的兩個數，大數m是小數n的倍數，那麼大數m即為所求的最小公倍數；若大數m不能被小數n整除則需要尋找一個能同時被兩數整除的自然數。

從大數m開始依次向後遞增直到找到第一個能同時被兩數整除的數為止，所以循環變數i的初值為尋找第一個能同時被兩整數整除的自然數，並將其輸出。需要注意的是，在找到第一個滿足條件的i值後，循環沒必要繼續下去，所以用break來結束循環。

#include<stdio.h>

int main()

{

int m, n, temp, i;

printf("Input m & n:");

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

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

{

temp = m;

m = n;

n = temp;

}

for(i=m; i>0; i++) /*從大數開始尋找滿足條件的自然數*/

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

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

printf("The LCW of %d and %d is: %d ", m, n, i);

break;

}

return 0;

}

(8)最小公倍數c語言演算法擴展閱讀：

c語言書寫規則：

1、一個說明或一個語句佔一行。

2、用{} 括起來的部分，通常表示了程序的某一層次結構。{}一般與該結構語句的第一個字母對齊，並單獨佔一行。

3、低一層次的語句或說明可比高一層次的語句或說明縮進若干格後書寫。以便看起來更加清晰，增加程序的可讀性。在編程時應力求遵循這些規則，以養成良好的編程風格。

網路-c語言

⑼ C語言窮舉法求最小公倍數

"對兩個正整數a,b,如果若干個a之和或b之和能被b所整除或能被a所整除，則該和數即為所求的最小公倍數。"這句話分開講會清楚一點：若干個a之和能被b所整除，或者，若干個b之和能被a所整除，那麼該和數即為所求的最小公倍數。但是這個說法有個錯誤，這個和可能有很多，只能叫公倍數，只有最小的才是最小公倍數。
的意思舉個例子：a=10，b=15。a*3
=
30，能被b=15整除，所以30是公倍數，60也行，但30是最小的，所以30是最小公倍數。如果從15看，兩個15，b*2
=
30，能整除10.。。。
這段程序的過程就是模擬這個演算法，先找到兩個數中較大的數p，然後判斷p是否能整除q，p*2是否能整除q，p*3是否能整除q。。。。。。直到找到能整除q的，就是最小公倍數了。為什麼是最小呢，因為p是從小到大開始找的，第一個找到的肯定是最小公倍數。

⑽ c語言求最小公倍數

1、首先介紹一下求最小公倍數的經典方法:

輾轉相除法
有兩整數a和b：
①a%b得余數c
②若c=0，則b即為兩數的最大公約數
③若c≠0，則a=b，b=c，再回去執行①
a*b除以最大公約數等於最小公倍數

2、因此原問題也化為最小公倍數和最大公約數一起求了。程序的演算法如下：

#include<stdio.h>

int lowest_common_multiple(int m,int n);

int main()

{

int m,n,c;

printf("請輸入m的值: ");

scanf("%d",&m);

printf("請輸入n的值: ");

scanf("%d",&n);

c=lowest_common_multiple( m, n);

printf("請輸出最小公倍數c的值: ");

printf("%d ",c);

return 0;

}

int lowest_common_multiple(int m,int n)

{

int remainder,m1,n1;

m1=m;

n1=n;

while (n != 0) {

remainder = m % n;

m = n;

n = remainder;

}

//printf("輸出最大公約數m: %d ", m); //此時的m為最大公約數

return m1*n1/m;

}

3、程序的輸出如下：

4、此題注釋的哪一個是輸出最大公約數的。