每日一题

DJ阿布 2011-08-18

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

albertshaw 2011-08-18

2*2*2*3*3*5*7=2520
2*2*2*2*3*3*5*7*11*13*17*19=232792560
求连续自然数的最小公倍数
然后归结于求该段自然数中的素数问题,这里我偷懒用的是BigInteger里面的isProbablePrime

DJ阿布 2011-08-18

albertshaw 写道

贴代码

albertshaw 2011-08-18

int length = 20;
int lcm = 0;
int temp = 0;
for (int i = 2; i <= length; i++) {
	if (BigInteger.valueOf(i).isProbablePrime(10)) {
		temp = i;
		while (temp * i <= length) {
			temp *= i;
		}
		lcm = lcm == 0 ? temp : lcm * temp;
	}
}
System.out.println(lcm);

代码真不好看,完全依赖于isProbablePrime能否判断正确

xianxg 2011-08-18

先求出2~20的素数放在数组prime[][2]的第0行中，第一行放的是该素数的几次方，初始为1.
然后对每个数或者说2~20中除了素数的数（data）执行下面的循环：
int[] j = new int[prime[0].length] //这个数组保存的是每个数能整除各个素数的几次方
for(int i=0; i < prime[0].length; i++){
    if(data % prime[i][0] == 0){
        data = data / prime[i][0];
        j[i]++;
        i--; //这里减一是为了下次还除以该素数，直到不能整除为止
    }
    else{    //如果不能整除，则查看被某个素数整除的次数是否大于保存的值
        if(j[i] > prime[i][1]) prime[i][1] = j[i];
    }
}

然后将prime数组的每个素数按照他们的第二行的数做几次方，最后再相乘就行了

llh110220 2011-08-19

采用map[int]int 来保存素数,key为素数，value为该素数的value次方，这个value次方的结果必须小于给定的上限,然后求出key**value的乘积即可

代码就不贴了

fxz_2008 2011-08-22

 
	function aaa(num1 , num2){  
		for(var i = Math.min(num1,num2) ; i > 0 ; i-- ){
			if( num1 % i == 0 && num2 % i == 0 ){ 
				return  num1 * num2 / i ;
			} 
		} 
	}
	
	var _all = 2 ;
	var _count = 20 ;
	
	for(var i = 2; i <= _count ; i++){
		_all = aaa(_all , i ) ;
	}
 
	document.write(_all);

DJ阿布 2011-08-22

albertshaw 写道

int length = 20;
int lcm = 0;
int temp = 0;
for (int i = 2; i <= length; i++) {
	if (BigInteger.valueOf(i).isProbablePrime(10)) {
		temp = i;
		while (temp * i <= length) {
			temp *= i;
		}
		lcm = lcm == 0 ? temp : lcm * temp;
	}
}
System.out.println(lcm);

代码真不好看,完全依赖于isProbablePrime能否判断正确

解法很漂亮~

DJ阿布 2011-08-22

fxz_2008 写道

 
	function aaa(num1 , num2){  
		for(var i = Math.min(num1,num2) ; i > 0 ; i-- ){
			if( num1 % i == 0 && num2 % i == 0 ){ 
				return  num1 * num2 / i ;
			} 
		} 
	}
	
	var _all = 2 ;
	var _count = 20 ;
	
	for(var i = 2; i <= _count ; i++){
		_all = aaa(_all , i ) ;
	}
 
	document.write(_all);

js解也很好
一点建议，有意义的方法名会显得更专业。

wentang 2011-08-26

（2*5*2）*19*（3*3）*17*（2*2）*7*13*11

发表回复

>>返回群组首页

每日一题

相关讨论

相关资源推荐