求最小公倍数
有两种方法
(1)分解质因数法
先把两个数用其质因数的乘积表示出来
如:求45和30的最小公倍数
45 = 3 * 3 * 5;
30 = 2 * 3 * 5;求出共有几种质因数，及每个质因数作为同一个数的质因数的乘积所用的最多的次数。
质因数共有2,3,5三种，3在45中重复两次，在30中只有一次，则取最大次为两次计算最小公倍数，为所有质因数的最大次方的积。
所以45和30的最小公倍数为90.
(2)公式法
- 求出两个数的乘积。
如:45和30的最小公倍数 45*30=1350 - 用这个乘积除以两数的最大公约数。
1350/15=90
c语言实现
#include<stdio.h>
int gcd(int a,int b)
{
if(a<b) return gcd(b,a);
int r;
while(r=a%b)
{
a = b;
b = r;
}
return b;
}
int main()
{
int a,b;
int sum;
while(scanf("%d %d",&a,&b)!=EOF)
{
sum = a*b/gcd(a,b);
printf("%d\n",sum);
}
return 0;
}
求最大公约数
(1)辗转相除法
设需求最大公约数的两数分别为a、b，且a>b
若a能够整除b，则b为最大公约数，否则另求a/b的余数作为a的值，再对a、b进行交换，保证a>b，进行下次判断。
c语言实现
int gcd(int a,int b)
{
if(a<b) return gcd(b,a);
int r;
while(r=a%b)
{
a = b;
b = r;
}
return b;
}
