C++020-C++因数，公因数，公倍数
在线练习：
因数，公因数，公倍数
在数学思维中，了解因数、公约数和公倍数的计算方法是十分必要的，本文的目标在于:
1、了解因数、公约数和公倍数的基本概念
2、掌握求解因数的基本步骤
3、掌握最大公约数和最小公倍数的求法
因数
因数，或称为约数，定义:整数a/整数b==整数c (b=0)而没有余数，我们就说b是a的因数。
注意:如果a/b==c且没有余数，那么能不能满足a/c==b且没有余数呢?所以如果b是a的因数，那么c也是a的因数。即因数大部分是成对出现的。
求解因数的枚举方法
#include<iostream> #include<stdio.h> #include <time.h> using namespace std; int main() { int n; cin>>n; for(int i=1;i<=n;i++) { if(n%i==0) { cout<<i<<" "; } } return 0; }
题目描述
【描述】任给一个正整数n,求这个数字的不同的因数及其个数。如n=6时，输出1,2,3,6四个因数，并且换行输出总数是4。
【输入】一个整数n;
【输出】两行;第一行从小到大列出因数，空格分隔;第二行是因数的数量。
【样例输入】
6
【样例输出】
1 2 3 6
4
#include<iostream> using namespace std; int main() { int n,s=0; cin>>n; for(int i=1;i<=n;i++) { if(n%i==0) { cout<<i<<" "; s++; } } cout<<endl<<s; return 0; }
最大公约数
最大公约数，也称最大公因数、最大公因子，指两个或多个整数共有约数中最大的一个。
4的因数有: 1、2、4
8的因数有: 1、2、4、8
则4和8的最大公约数为4。
求解最大公约数的方法：
枚举法
可以使用枚举的方法：从最大的因数开始去除，看两个数字是否都能整除，如果找到第一个那么这个数字就是最大公约数。
#include<iostream> using namespace std; int main() { int a,b; cin>>a>>b; for(int i=min(a,b);i>=1;i--) { if(a%i==0 && b%i==0) { cout<<i; break; } } return 0; }
辗转相除法
辗转相除法是求最大公约数的一种方法。它的具体做法是:
用较大数m除较小数n，得到的余数r作为下次运算中的较小数m，原来的n作为下次运算中的较大数。
如此反复，直到最后余数是O为止，最后的除数就是这两个数的最大公约数。
例如:
对于整数m=12和整数n=8。
12 %8得到余数r=4,将n的值给m,将r的值给n
8 %4得到余数r=0;
r为0，运算结束，则除数n=4就是最大公约数
#include<iostream> using namespace std; int main() { int a,b,t; cin>>a>>b; if(a<b) swap(a,b); // 确保a比b大 // for(;a%b;) while(a%b) { t=a%b;//保存余数 a=b; // 把较小的b赋值给a b=t; //把余数赋值给b } cout<<b<<endl; return 0; }
最小公倍数
两个或多个整数公有的倍数叫做它们的公倍数，其中除O以外最小的一个公倍数就叫做这几个整数的最小公倍数。
对于整数4和整数8。
4的倍数有:4、8、12…
8的倍数有:8、16、32
则4和8的最小公倍数为8。
求解最小公倍数的方法
枚举法
利用枚举的思想，把任意一个数的倍数从小到大求余另外一个数字，如果能整除，就是最小公倍数。
#include<iostream> using namespace std; int main() { int a,b,i=1; cin>>a>>b; while(1) { if(a*i % b==0) { cout<<i*a; break; } i++; } return 0; }
用最大公约数找最小公倍数
由于两个数的乘积等于这两个数的最大公约数(x)与最小公倍数(y)的积，可以利用最大公约数求两个数字m和n 的最小公倍数m*n==x*y
步骤:
求两个数字的最大公约数，设为x
m/x*n得到m和n的最大公约数
#include<iostream> using namespace std; int gcd(int x,int y) { if(x<y) swap(x,y); while(x%y) { int t=x%y; x=y; y=t; } return y; } int main() { int a,b,g; cin>>a>>b; int t = gcd(a,b); a = a/t; b = b/t; g = a*b *t; cout<<g; return 0; }
题目描述-已知最大公约数和最小公倍数，求原数
【描述】已知两个数a和b的最大公约数是G，最小公倍数是L，问这两个数可能是多少?列出所有的解。注意，a=3,b=4和a=4，b=3算不同的解。
【输入】两个整数G和L;均在int范围内;
【输出】若干行，一组解占一行;按照a从小到大列出所有解。
【样例输入】
14
280
【样例输出】
14 280
56 70
70 56
280 14
【分析】
两个数可以表示为
a=a1*a2*a3*...*an*G b=b1*b2*b3*..*bn*G L =a1*a2*....n*b1*b2*...*bn*G 其中G是a和b中因数的交集，即产生最大公约数的部分因数，那么a1...an与b1...bn没有公因数。 不妨设a=A*G，b=B*G，那么AB=L/G，且AB的最大公约数为1; 我们枚举A和B的组合，就能从A和B计算得到a和b。
#include<iostream> using namespace std; int gcd(int x,int y) { if(x<y) swap(x,y); while(x%y) { int t=x%y; x=y; y=t; } return y; } int main() { int a,b,G,L,A,B; cin>>G>>L; int t=L/G; for(A=1;A<=t;A++) { if(t%A==0) { B=t/A; if(gcd(A,B)==1) { cout<<A*G<<" "<<B*G<<endl; } } } return 0; }
作业
在线练习：
总结
本系列为C++学习系列，会介绍C++基础语法，基础算法与数据结构的相关内容。本文为C++中的因数、公因数、公倍数案例，包括相关案例练习。
