//书本第四章第01题,分别求出两个整数的最大公约数和最小公倍数,用主函数调用两个函数,并输出结果,两个整数由键盘输入。
/*
最小公倍数_--解法一
借助最大公约数求最小公倍数
步骤:
一、利用辗除法或其它方法求得最大公约数;
二、 最小公倍数等于两数之积除以最大公约数。
最小公倍数--解法二
质因数分解
举例:12和27的最小公倍数 12=2×2×3 27=3×3×3
必须用里面数字中的最大次方者,像本题有3和3的立方,
所以必须使用3的立方(也就是3*3*3),不能使用3
所以: 2×2×3×3×3=4×27=108
两数的最小公倍数是108
最大公约数原理
如果有一个自然数a能被自然数b整除,则称a为b的倍数,b为a的约数。
几个自然数公有的约数,叫做这几个自然数的公约数。公约数中最大的一个公约数,称为这几个自然数的最大公约数。
例: 在2、4、6中,2就是2,4,6的最大公约数。
早在公元前300年左右,欧几里得就在他的著作《几何原本》中给出了高效的解法——辗转相除法。
辗转相除法使用到的原理很聪明也很简单,假设用f(x, y)表示x,y的最大公约数,
取k = x/y,b = x%y,则x = ky + b,
如果一个数能够同时整除x和y,则必能同时整除b和y;
而能够同时整除b和y的数也必能同时整除x和y,
即x和y的公约数与b和y的公约数是相同的,其最大公约数也是相同的,
则有f(x, y)= f(y, y % x)(y > 0),
如此便可把原问题转化为求两个更小数的最大公约数,
直到其中一个数为0,剩下的另外一个数就是两者最大的公约数。
例如,12和30的公约数有:1、2、3、6,其中6就是12和30的最大公约数。
*/
//第四章第01题,分别求出两个整数的最大公约数和最小公倍数,用主函数调用两个函数,并输出结果,两个整数由键盘输入。
#include<iostream>
using namespace std;
//辗转相除法
inline int gongyue(int x,int y)
{
int t;
if(x>y)t=y,y=x,x=t; //将较大数赋给y,xy顺序调换
if(x!=0)gongyue(x,t=y%x);//辗转相除法及递归调用,[公约数(较小数,余数)]
else return y;
}
int main()
{
//输入整数
cout<<"请输入两个整数并用空格间开:";
int a,b;
cin>>a>>b;cout<<endl;
//运算
int i=gongyue(a,b);
cout<<"它们的最大公约数是:"<<i<<endl;
i=a*b/i;
cout<<"它们的最小公倍数是:"<<i<<endl;
return 0;
}
分享到:
相关推荐
关于如何求最大公约数和最小公倍数的c语言程序
用LabVIEW求最大公约数和最小公倍数。可以自行选择数据。
基于FPGA开发板的两位数求最大公约数和最小公倍数的设计,该设计中利用辗转相减法求得公约数与公倍数,且两个数的数值可通过按键修改,设计灵活可靠。该设计基于vivado开发,并带有testbench文件,方便仿真学习。
1.最小公倍数、最大公约数1.最小公倍数、最大公约数1.最小公倍数、最大公约数
求m和n的最小公倍数和最大公约数 用于求m和n 的最小公倍数和最大公约数的C#源代码
c#求最小公倍数、最大公约数。。。。。。。。
求两个数的最小公倍数和最大公约数C++,编程环境在VS2010下以实验。
2.编写两个函数,分别求两个整数的最大公约数和最小公倍数
python求最大公约数和最小公倍数 #辗转相除法 def gcd(a,b): #最大公约数函数,且最小公倍数 = 两个数相乘 / 最大公约数 if b == 0: return a else: return gcd(b,a%b) print("请输入两个数:") j,k = input()....
求两个整数的最大公约数和最小公倍数的C语言方法
计算任意几个数的最小公倍数和最大公约数(简单方式\有子VI)
python 输入两个正整数计算最大公约数和最小公倍数 示例
Java求最大公约数、最小公倍数,输入两个正整数m和n,求其最大公约数和最小公倍数。最小公倍数可由原数除以最大公约数计算得到,这里使用了辗除法。
c++求最大公因数和最小公倍数,利用最大公因数法求最小公倍数。
求最大公约数和最小公倍数的程序,求两个整数的最大公约数和最小公倍数!
JAVA实现求最大公约数和最小公倍数 根据欧几里得定律,最大公约数的递归算法
用碾压法求出两个数的最大公因数,然后将剩下的分子连乘再乘以最大公因数即可获得最小公倍数
包含了:1.辗转相除法函数嵌套流程图2.辗转相除法函数递归流程图3.穷举法求最小公倍数流程图4.穷举法求最大公约数流程图5.更相减损术流程图
求最大公约数和最小公倍数. 相信你们会找到的。