求最小公倍數(shù)
有兩種方法
(1)分解質(zhì)因數(shù)法
先把兩個數(shù)用其質(zhì)因數(shù)的乘積表示出來
如:求45和30的最小公倍數(shù)
45 = 3 * 3 * 5;
30 = 2 * 3 * 5;求出共有幾種質(zhì)因數(shù)暮胧，及每個質(zhì)因數(shù)作為同一個數(shù)的質(zhì)因數(shù)的乘積所用的最多的次數(shù)。
質(zhì)因數(shù)共有2,3,5三種，3在45中重復(fù)兩次及汉，在30中只有一次佣谐，則取最大次為兩次計算最小公倍數(shù)陡鹃，為所有質(zhì)因數(shù)的最大次方的積明未。
所以45和30的最小公倍數(shù)為90.
(2)公式法
- 求出兩個數(shù)的乘積钧唐。
如:45和30的最小公倍數(shù) 45*30=1350 - 用這個乘積除以兩數(shù)的最大公約數(shù)轩触。
1350/15=90
c語言實現(xiàn)
#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;
}
求最大公約數(shù)
(1)輾轉(zhuǎn)相除法
設(shè)需求最大公約數(shù)的兩數(shù)分別為a寞酿、b，且a>b
若a能夠整除b脱柱，則b為最大公約數(shù)伐弹，否則另求a/b的余數(shù)作為a的值，再對a榨为、b進行交換惨好，保證a>b，進行下次判斷随闺。
c語言實現(xiàn)
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;
}
