php专区

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

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

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

int get_lcm(int a, int b)
{
	if(a==b)
	{
		return a;
	}
	int bigger = a
  
  	
另外一种比较好的方法，以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，欢迎访问原出处。