求两个正整数m,n的最大公约数算法。
【分析】:求两个正整数的最大公约数可以采用 辗转相除 的算法,分别用m,n,r表示被除数,除数,和余数。
(1) 求m除以n得到的余数r。
(2)判断 r == 0,算法结束,则n为两个数的最大公约数。
r!=0,则把n赋值给m,r赋值给n,在做m除以n
(3) 转到第二步继续进行。。。。直到 r == 0 为止,输出n的大小。
# include<cstdio> # include<iostream> using namespace std; int main(void) { int m,n; cin>>m>>n; int r = m%n; while ( r != 0 ) { m = n; n = r; r = m%n; } cout<<n<<endl; return 0; }
如果题目中要求我们求解 最小公倍数,那么我们只要记住这一条非常好用的公式就行。。。。
m*n = 最大公约数*最小公倍数~