被1至20整除的最小正整数问题

一个思考的小捷径
服务器君一共花费了578.242 ms进行了4次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

求能被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。

本文地址:http://www.nowamagic.net/librarys/veda/detail/939,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/939

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《代码大全(第2版)》 史蒂夫•迈克康奈尔 (Steve McConnell) (作者), 金戈 (译者)

代码大全(第2版)是著名IT畅销书作者、《IEEE Software》杂志前主编、具有20年编程与项目管理经验的Steve McConnell十余年前的经典著作的全新演绎:第2版做了全面的更新,增加了很多与时俱进的内容,包括对新语言、新的开发过程与方法论的讨论等等。这是一本百科全书式的软件构建手册,涵盖了软件构建活动的方方面面,尤其强调提高软件质量的种种实践方法。

更多计算机宝库...