求最小公倍数

有两种方法

(1)分解质因数法

1. 先把两个数用其质因数的乘积表示出来
   如:求45和30的最小公倍数
   45 = 3 * 3 * 5;
   30 = 2 * 3 * 5;

2. 求出共有几种质因数，及每个质因数作为同一个数的质因数的乘积所用的最多的次数。
   质因数共有2,3,5三种，3在45中重复两次，在30中只有一次，则取最大次为两次

3. 计算最小公倍数，为所有质因数的最大次方的积。
   所以45和30的最小公倍数为90.

(2)公式法

1. 求出两个数的乘积。
   如:45和30的最小公倍数 45*30=1350
2. 用这个乘积除以两数的最大公约数。
   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)辗转相除法

1. 设需求最大公约数的两数分别为a、b，且a>b

2. 若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;
}