C 020-C 因数，公因数，公倍数
在线练习： http://noi.openjudge.cn/ https://www.luogu.com.cn/
因数，公因数，公倍数
在数学思维中，了解因数、公约数和公倍数的计算方法是十分必要的，本文的目标在于:
1、了解因数、公约数和公倍数的基本概念 2、掌握求解因数的基本步骤 3、掌握最大公约数和最小公倍数的求法
因数
因数，或称为约数，定义:整数a/整数b==整数c (b=0)而没有余数，我们就说b是a的因数。 注意:如果a/b==c且没有余数，那么能不能满足a/c==b且没有余数呢?所以如果b是a的因数，那么c也是a的因数。即因数大部分是成对出现的。
求解因数的枚举方法
代码语言：javascript复制#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
代码语言：javascript复制#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。
求解最大公约数的方法：
枚举法
可以使用枚举的方法：从最大的因数开始去除，看两个数字是否都能整除，如果找到第一个那么这个数字就是最大公约数。
代码语言：javascript复制#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为止，最后的除数就是这两个数的最大公约数。
例如:
代码语言：javascript复制对于整数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。
求解最小公倍数的方法
枚举法
利用枚举的思想，把任意一个数的倍数从小到大求余另外一个数字，如果能整除，就是最小公倍数。
代码语言：javascript复制#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 步骤:
代码语言：javascript复制求两个数字的最大公约数，设为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 【分析】 两个数可以表示为
代码语言：javascript复制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;
}
作业
在线练习：
http://noi.openjudge.cn/
总结
本系列为C 学习系列，会介绍C 基础语法，基础算法与数据结构的相关内容。本文为C 中的因数、公因数、公倍数案例，包括相关案例练习。
