0

最近有另一个 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;
     };
4

8 回答 8

6

收集 1 到 20 之间所有数字的质因数。计算每个质因数的最大指数，我们有16 = 2**4，9 = 3**2，以及 5、7、11、13、17、19（每个仅出现一次）。乘以很多，你就有了答案。

于 2008-10-11T01:08:16.317 回答
3

在 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;
}

?>

它至少比您发布的速度快两倍。

于 2008-10-11T01:37:24.247 回答
2

克里斯·杰斯特-杨是对的。

一般来说，如果你想要能被从 1 到 N 的所有数整除的最小数，你会想要找到从 2 到 N 的所有素数，并且对于每个素数，找出它除以任何素数的最大次数。范围内的数字。这可以通过找到不大于 N 的素数的最大幂来计算。

在 20 的情况下，正如 Chris 指出的，2^4 是 2 不大于 20 的最大幂，3^2 是 3 不大于 20 的最大幂，对于所有其他素数，只有一次幂不大于 20。

于 2008-10-11T01:14:50.720 回答
2

您可以删除一些被除以的数字，例如 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();
?>
于 2008-10-11T04:29:10.093 回答
1 
<?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 解决方案，这是一个不错的算法。

于 2009-01-23T23:08:47.503 回答
0

有些人真的想多了……

在红宝石中：

puts 5*7*9*11*13*16*17*19
于 2009-06-18T04:19:50.927 回答
0

@人们做简单的数学；我不确定这是否是练习的目标。你要学习新的语言和新的表演方式。仅仅通过计算器进行计算并不是正确的处理方式。

而且我知道这是一个旧帖子中的帖子，但它仍然出现在谷歌搜索结果中:)

用代码（即 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 倍

于 2011-06-07T08:57:47.430 回答
-1

我知道你说的是 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)

它没有我能做到的那么优雅，但它可以在 0.15 秒内计算从 2 到 2000 的数字的最小公倍数。如果您的迭代解决方案每秒可以处理十亿个候选者，则需要 10^849 年才能完成。

换句话说，不要费心优化错误的算法。

于 2008-10-11T05:00:02.560 回答