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

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

求能被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本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

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

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

《高性能网站建设指南》 桑德斯 (Steve Sounders) (作者), 刘彦博 (译者)

《高性能网站建设指南》结合Web2.0以来Web开发领域的最新形势和特点,介绍了网站性能问题的现状、产生的原因,以及改善或解决性能问题的原则、技术技巧和最佳实践。重点关注网页的行为特征,阐释优化Ajax、CSS、JavaScript、Flash和图片处理等要素的技术,全面涵盖浏览器端性能问题的方方面面。在《高性能网站建设指南》中,作者给出了14条具体的优化原则,每一条原则都配以范例佐证,并提供了在线支持。全书内容丰富,主要包括减少HTTP请求、ExpiresHeader技术、Gzip组件、CSS和JavaScript最佳实践、关闭ETags的技巧、Ajax缓存技术和最小化技术等。

更多计算机宝库...