简明现代魔法 -> 计算机算法 -> 求能被1到20的数整除的最小正整数

求能被1到20的数整除的最小正整数

2011-01-20

求能被1到20的数整除的最小正整数。最直觉的方法是求1到20这20个数的最小公倍数。

求n个数的最小公倍数,以a,b,c三个数为例,他们的最小公倍数等于:先求a与b的最小公倍数m,然后m和c的最小公倍数即着三个数的最小公倍数。

求两个数a,b的最小公倍数嘛,先取出其中较大的那个比如a,然后再用k*a去试探能否被较小那个数整除,其中,k是从1开始的自然数 k*a<a*b。

int get_lcm(int a, int b)
{
	if(a==b)
	{
		return a;
	}
	int bigger = a<b?b:a;
	int smaller= a<b?a:b;
	int max = a*b;
	int i;
	for(i=bigger; i<max; i+=bigger)
	{
		if(i%smaller == 0)
		{
			return i;
		}
	}
	return max;
}

另外一种比较好的方法,以n取10为例

2,3,4,5,6,7,8,9,10 (1没有什么意义,忽略掉了)

将这些数字分解质因数:

2, 3, 2*2, 5, 2*3, 7, 2*2*2, 3*3, 2*5

这些质数分别是2, 3, 5, 7

最终答案可以表示为:

2^a * 3^b * 5^c * 7^d (其中,x^y表示x的y次方)

其中的英文字母表示在上面分解质因数时所得到的表达式中质因数在同一个表达式中出现的次数的最大值。

质因数2出现次数最多是在8=2*2*2中,其出现了3次,所以a为3。

同理可得到:2^3 * 3^2 * 5^1 * 7^1 = 2520。

随机文章推荐
网站分类


注:如需转载本文,请注明出处(原文链接),谢谢。更多精彩内容,请进入简明现代魔法首页。

进入新博客
喜欢本文,就分享它吧
给我留言
您的名字:
您的邮件:
您的网站:


 

copyright © 2009 简明现代魔法    学习、分享、进步

power by Gonn 感谢所有关心和支持本站的朋友们