两个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，……直到余数为零为止