兩個m和n的計算方法

『壹』 求兩個正整數m和n的最大公約數

求兩個正整數的最大公約數的演算法通常使用「輾轉相除法」。設有兩個正整數m、n，求它們的最大公約數的演算法如下：
①若m＜n，則交換m和n（保證m大於n）。
②計算m/n的余數r。
③若r不等於0，則令m＝n、n＝r，轉第②步繼續執行；
否則，演算法結束，n就是最大公約數。
下面就是用「輾轉相除法'才出並返回m、n最大公約數的函數fmn（），請填寫清單中缺少的語句。
int fmn（ m, n）
int m， n；
｛ int r；
if（m＜n ）
{r＝m；m＝n；n＝r；}
if（n＝＝0）
return（m）；
do{_________________
if（r!= 0）
{ m＝n； n＝r；}
}while（r!=0）；
return（n）；
}
【分析】由於演算法步驟已經給出，按照演算法來理解程序就比較簡單。函數體開始的單分支語
句是確保m值是大於n值的。接下來的單分支語句是確保演算法中的除法「m／n」時的除數n不為0。注意，如果一開始的n就是O，則兩個最大公約數就是m，此處利用返回語句返回的函數值就是m。接下來的do－while循環是實現演算法步驟中的第②步和第③步的，顯然該循環體中的第2條單分支語句是完成演算法步驟中的第③步工作的，而空白處應該完成演算法步驟中的第②步工作，即r等於m／n的余數。
【答案】r＝m％n；
【說明】求最大公約數和最小公倍數的演算法是常用演算法；但在教材中並沒有給出，希望讀者在
學有餘力的情況下，能掌握這兩個演算法。
求兩個正整數的最小公倍數的演算法在教材中也沒有給出，下面給出求最小公倍數的一種演算法。設有兩個正整數m、n，求它們的最小公倍數的演算法如下：
①若m＜n，則交換m和n（保證m大於n）。
②令d＝m。
③若d能被n整除，則演算法結束，d就是m和n的最小公倍數。
否則，令d＝d＋m，轉第③步，繼續執行。
實現演算法的程序清單如下：
main（）
{ int m， n， d ；
scanf（"％d，％d"，＆m，＆n）；
if（m＜n）
{ d=m；m＝n；n＝d；}
if（n＝＝0）
d＝0；
else
{ d＝m；
while（d％n!=0）
d＋＝m；
}
printf（」％d＼n」，d）；
}

『貳』 輸入兩個正整數m和n，求其最大公約數和最小公倍數

#include<stdio.h>

int main(){

int a,b,num1,num2,temp;

printf("please input two number: ");

scanf("%d%d",&num1,&num2);

if(num1<num2){

temp = num1;

num1 = num2;

num2 = temp;

}

a = num1;

b = num2;

while(b!=0){

temp = a%b;

a=b;

b=temp;

}

printf("gongyueshu:%d ",a);

printf("gongbeishu:%d ",num1*num2/a);

}

(2)兩個m和n的計算方法擴展閱讀：

兩個整數的最大公約數主要有兩種尋找方法：

* 兩數各分解質因數，然後取出同樣有的質因數乘起來

*輾轉相除法（擴展版）

和最小公倍數（lcm）的關系：

gcd(a, b) * lcm(a, b) = ab

a與b有最大公約數，

兩個整數的最大公因子可用於計算兩數的最小公倍數，或分數化簡成最簡分數。

兩個整數的最大公因子和最小公倍數中存在分配律：

* gcd(a, lcm(b, c)) = lcm(gcd(a, b), gcd(a, c))

* lcm(a, gcd(b, c)) = gcd(lcm(a, b), lcm(a, c))

在坐標里，將點(0, 0)和(a, b)連起來，通過整數坐標的點的數目（除了(0, 0)一點之外）就是gcd(a, b)。

『叄』 C語言編程，輸入兩個正整數M和N（M<N），計算M和N之間的所有整數和

一、基本方法：

1、輸入M和N；

2、遍歷從M到N的所有整數；

3、每個累加；

4、輸出結果。

參考代碼：

#include<stdio.h>
intmain()
{
intM,N,n,s=0;
scanf("%d%d",&M,&N);//輸入
for(n=M;n<=N;n++)//遍歷
s+=n;//累加每個整數。
printf("%d
",s);//輸出結果。
return0;
}

二、利用等差數列求和公式。

從M到N的所有整數為等差數列，公差為1，所以可以利用求和公式直接獲得結果。

#include<stdio.h>
intmain()
{
intM,N,n,s=0;
scanf("%d%d",&M,&N);//輸入
s=(M+N)*(N-M+1)/2;//等差數列求和。
printf("%d
",s);//輸出結果。
return0;
}

三、方法對比：

第一種適用於C語言練習，可以涉及更多知識點。

第二種方法效率更高，適用於實際應用。

『肆』 求兩個自然數M和N的最大公約數.

如果M和N是互質數,則M和N的最大公約數是1,
如果M和N是倍數關系,則M和N的最大公約數是較小數,
如果M和N既不是互質數也不是倍數關系,則用短除法求．

『伍』 編寫程序：輸入兩個正整數m和n，計算它們的最大公約數和最小公倍數。

#include<iostream>
using namespace std ;

//最大公約數-Greatest Common Divisor
int gcd(int m, int n)
{
return n == 0 ? m : gcd(n, m % n) ;
}

//最小公倍數-Least Common Multiple
int lcm(int m, int n)
{
return m * n / gcd(m, n) ;
}

int main(void)
{

int m ;
cout << "input m: " ;
cin >> m ;

int n ;
cout << "input n: " ;
cin >> n ;

cout << "The greatest common divisor is:" ;
cout << gcd(m, n) << endl ;

cout << "The least common multiple is: " ;
cout << lcm(m, n) << endl ;

system("pause") ;
return 0 ;
}

『陸』 輸入兩個正整數m和n，求其最大公約數和最小公倍數。

你網路下，我發網址通不過。。
輸入兩個正整數m和n, 求其最大公約數和最小公倍數.

<1> 用輾轉相除法求最大公約數
演算法描述:
m對n求余為a, 若a不等於0
則 m <- n, n <- a, 繼續求余
否則 n 為最大公約數
<2> 最小公倍數 = 兩個數的積 / 最大公約數

#include
int main()
{
int m, n;
int m_cup, n_cup, res; /*被除數, 除數, 余數*/
printf("Enter two integer:\n");
scanf("%d %d", &m, &n);
if (m > 0 && n >0)
{
m_cup = m;
n_cup = n;
res = m_cup % n_cup;
while (res != 0)
{
m_cup = n_cup;
n_cup = res;
res = m_cup % n_cup;
}
printf("Greatest common divisor: %d\n", n_cup);
printf("Lease common multiple : %d\n", m * n / n_cup);
}
else printf("Error!\n");
return 0;
}

★ 關於輾轉相除法, 搜了一下, 在我國古代的《九章算術》中就有記載，現摘錄如下:

約分術曰：「可半者半之，不可半者，副置分母、子之數，以少減多，更相減損，求其等也。以等數約之。」

其中所說的「等數」，就是最大公約數。求「等數」的辦法是「更相減損」法，實際上就是輾轉相除法。

輾轉相除法求最大公約數，是一種比較好的方法，比較快。

對於52317和75569兩個數，你能迅速地求出它們的最大公約數嗎？一般來說你會找一找公共的使因子，這題可麻煩了，不好找，質因子大。

現在教你用輾轉相除法來求最大公約數。

先用較大的75569除以52317，得商1，余數23252，再以52317除以23252，得商2，余數是5813，再用23252做被除數，5813做除數，正好除盡得商數4。這樣5813就是75569和52317的最大公約數。你要是用分解使因數的辦法，肯定找不到。

那麼，這輾轉相除法為什麼能得到最大公約數呢？下面我就給大夥談談。

比如說有要求a、b兩個整數的最大公約數，a＞b，那麼我們先用a除以b，得到商8，余數r1：a÷b＝q1…r1我們當然也可以把上面這個式子改寫成乘法式：a＝bq1＋r1------l）

如果r1＝0，那麼b就是a、b的最大公約數3。要是r1≠0，就繼續除，用b除以r1，我們也可以有和上面一樣的式子：

b＝r1q2＋r2-------2）

如果余數r2＝0，那麼r1就是所求的最大公約數3。為什麼呢？因為如果2）式變成了b＝r1q2，那麼b1r1的公約數就一定是a1b的公約數。這是因為一個數能同時除盡b和r1，那麼由l）式，就一定能整除a，從而也是a1b的公約數。

反過來，如果一個數d，能同時整除a1b，那麼由1）式，也一定能整除r1，從而也有d是b1r1的公約數。

這樣，a和b的公約數與b和r1的公約數完全一樣，那麼這兩對的最大公約數也一定相同。那b1r1的最大公約數，在r1＝0時，不就是r1嗎？所以a和b的最大公約數也是r1了。

有人會說，那r2不等於0怎麼辦？那當然是繼續往下做，用r1除以r2，……直到余數為零為止