最近还有一个Project Euler的问题，但我认为这有点具体（我只对基于PHP的解决方案感兴趣），所以我还是在问。
问题5问你："能被1到20的所有数字整除的最小数字是什么？"
现在，我已经解决了两次。一次效率很低，一次效率更高，但我离一个特别复杂的答案还很远（我的数学不是特别扎实，因此我的强力解决方案）。我可以看到我可以改进的几个方面，但我想知道你们中是否有人能证明这个问题的更有效的解决方案。
*剧透：这是我的不太理想（运行7秒），但仍然可以忍受的解决方案（不确定该怎么办双$…只是假装你只看到1…
function euler5(){
$x = 20;
for ($y = 1; $y < 20; $y++) {
if (!($x%$y)) {
} else {
$x+=20;
$y = 1;
}
}echo $x;
};
为1到20之间的所有数字收集素数。计算每个素因子的最大指数，我们有16 = 2**4，9 = 3**2，以及5，7，11，13，17，19（每个只出现一次）。把这个数字相乘，你就有答案了。
在php中，它看起来像这样：
<?php
function gcd($a,$b) {
while($a>0 && $b>0) {
if($a>$b) $a=$a-$b; else $b=$b-$a;
}
if($a==0) return $b;
return $a;
}
function euler5($i=20) {
$euler=$x=1;
while($x++<$i) {
$euler*=$x/gcd($euler,$x);
}
return $euler;
}
?>
它的速度至少是你发布的速度的两倍。
Chris Jester Young是对的。
一般来说，如果你想要一个最小的数，它可以被从1到N的所有数整除，你会想要找到从2到N的全部素数，对于每一个素数，都要找到它除以该范围内任何数的最大次数。这可以通过找到不大于N的素数的最大幂来计算。
在20的情况下，正如克里斯所指出的，2^4是不大于20的2的最大幂，3^2是不大于20%的3的最大幂。对于所有其他素数，只有一次幂不大于20。
您可以删除一些被除的数字，例如1是不必要的，所有自然数都可以被1整除。您也不需要2，因此，所有数字都可以被2的倍数整除（4、8、16等）也可以被2整除。因此，相关的数字将是11、12、13、14、15、16、17、18和19。
因此：
<?
function eulerPuzzle()
{
$integers = array( 11,12,13,14,15,16,17,18,19 );
for ($n = 20; 1; $n += 20 ) {
foreach ($integers as $int) {
if ( $n % $int ) {
break;
}
if ( $int == 19 ) {
die ("Result:" . $n);
}
}
}
}
eulerPuzzle();
?>
<?php
$i=20;
while ($i+=20) {
for ($j=19;$j!==10;--$j){
if ($i%$j) continue 2;
}
die ("result: $i'n");
}
是迄今为止最快、最短的php解决方案。在我的电脑上比Czimi快1.4倍。但是看看python的解决方案，这是一个不错的算法。
有些人真的想得太多了。。。
Ruby中：
puts 5*7*9*11*13*16*17*19
@做简单数学的人；我不确定这是否是练习的目标。你要学习新的语言和新的表演方式。仅仅用计算器计算是不对的。
我知道这是一个旧帖子，但它仍然出现在谷歌结果中：）
用代码（就是PHP）做这件事，我发现这是最快的解决方案：
function eulerPuzzle() {
$integers = array (11, 12, 13, 14, 15, 16, 17, 18, 19 );
for($n = 2520; 1; $n += 2520) {
foreach ( $integers as $int ) {
if ($n % $int) {
break;
}
if ($int == 19) {
die ( "Result:" . $n );
}
}
}
}
eulerPuzzle ();
是的，这是CMS的修改作品。它更快的主要原因是，当你阅读问题时，他们已经指出前10个整数的最低可能数是2520。因此，您可以只增加2520，而不是20。导致循环次数减少126次
我知道你说的是PHP，但这是我用Python写的草稿。
#!/usr/bin/env python
from operator import mul
def factor(n):
factors = {}
i = 2
while i < n and n != 1:
while n % i == 0:
try:
factors[i] += 1
except KeyError:
factors[i] = 1
n = n / i
i += 1
if n != 1:
factors[n] = 1
return factors
base = {}
for i in range(2, 2000):
for f, n in factor(i).items():
try:
base[f] = max(base[f], n)
except KeyError:
base[f] = n
print reduce(mul, [f**n for f, n in base.items()], 1)
它没有我能做的那么优雅，但它计算出了从2到2000的最小公倍数，在.15秒内。如果你的迭代解决方案每秒能处理10亿个候选者，那么它将需要10^849年才能完成。
换句话说，不要麻烦优化错误的算法。