最大公约数和最小公倍数算法

先用辗转相除法求出最大公约数，然后再利用（最小公倍数=两数乘积/最大公约数）求得最小公倍数。

辗转相除算法：

//非递归算法
int gcd(int a, int b) 
{
	int temp;
	if(a < b) //swap(a,b) 交换a和b
	{
		temp=b;
		b=a;
		a=temp;
	}
	temp=0;
	while((temp = a % b) != 0) //辗转相除 
	{ 
		a = b; 
		b = temp; 
	}
	return b; 
}
//递归算法
int gcd (int a,int b)
{
    if (b==0)
        return a;
    return gcd(b,a%b);
}

计算法N个数的最大公约数算法：

int ngcd(int *pa, int n) 
{
	if(n == 1)
		return *pa;
	return (gcd(pa[n-1], ngcd(pa, n-1)));
}

计算最小公倍数算法：

int lcm(int a, int b) //最小公倍数 ＝ 两数乘积 / 最大公约数 
{
	return a*b/gcd(a, b); 
}

计算N个数的最小公倍数的算法：

int nlcm(int *pa, int n) 
{
	if(n == 1)
		return *pa;
	return lcm(pa[n-1], nlcm(pa, n-1)); 
}

例：

#include <stdio.h>

//int gcd(int a, int b); //两个数的最大公约数 
//int ngcd(int *pa, int n) //N个数的最大公约数 
//int lcm(int a, int b) //两个数的最小公倍数 
//int nlcm(int *pa, int n) //N个数的最小公倍数

int gcd (int a,int b)
{
    if (b==0)
        return a;
    return gcd(b,a%b);
}

int ngcd(int *pa, int n) 
{
	if(n == 1)
		return *pa;
	return (gcd(pa[n-1], ngcd(pa, n-1)));
}

int lcm(int a, int b) //最小公倍数 ＝ 两数乘积 / 最大公约数 
{
	return a*b/gcd(a, b); 
}

int nlcm(int *pa, int n) 
{
	if(n == 1)
		return *pa;
	return lcm(pa[n-1], nlcm(pa, n-1)); 
}


int main()
{
	int a,b,n,rgcd,rlcm,rngcd,rnlcm;
	int pa[10];
	printf("please input tow number:");
	scanf("%d %d",&a,&b);
	rgcd=gcd(a,b);
	rlcm=lcm(a,b);
	printf("最大公约数是：%d/n",rgcd);
	printf("最小公倍数是：%d/n",rlcm);
	printf("please input the n:");
	scanf("%d",&n);
	for (int i=0;i<n;i++)
		scanf("%d",&pa[i]);
	rngcd=ngcd(pa,n);
	rnlcm=nlcm(pa,n);
	printf("最大公约数是：%d/n",rngcd);
	printf("最小公倍数是：%d/n",rnlcm);
	return 0;
}

HDU 1108 最小公倍数

Problem Description

给定两个正整数，计算这两个数的最小公倍数。

Input

输入包含多组测试数据，每组只有一行，包括两个不大于1000的正整数.

Output

对于每个测试用例，给出这两个数的最小公倍数，每个实例输出一行。

Sample Input

10 14

Sample Output

70

Source

POJ

Recommend

Eddy

AC 代码：

#include <stdio.h>

int gcd (int a,int b)
{
    if (b==0)
        return a;
    return gcd(b,a%b);
}
int main()
{
    int a,b;
    while (scanf("%d%d",&a,&b)!=EOF)
    {
        int x=gcd(a,b);
        printf("%d/n",(a*b)/x);
    }
    return 0;
}