项目Euler Puzzler（特别是在PHP中）

Question

最近有另一个项目欧拉问题，但我认为这有点具体（我只对基于PHP的解决方案感兴趣），所以无论如何我都在问。

有帮助吗？

提交

解决方案

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

?>

它的速度至少是你发布的速度的两倍。

Answer 1

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

?>

它的速度至少是你发布的速度的两倍。

Answer 2

收集1到20之间所有数字的素数因子。计算每个素数因子的最大指数，我们有16 = 2**4，9 = 3**2，以及5,7,11,13,17,19（每个都出现）只有一次）。将该批次乘以，您就得到了答案。

Answer 3

Chris Jester-Young是对的。

一般情况下，如果你想要从1到N的所有数字均匀分割的最小数字，你可能希望找到从2到N的所有素数，并且对于每一个，找到最多的次数它除了范围内的任何数字。这可以通过找到不大于N的素数的最大幂来计算。

在20的情况下，克里斯指出，2 ^ 4是2的最大幂不大于20,3 ^ 2是3的最大幂不大于20，并且对于所有其他素数，仅第一个权力不超过20。

Answer 4

你可以删除一些被划分的数字，例如1是不必要的，所有自然数都可以被1整除。你不需要2，因此，所有数字都可被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();
?>

Answer 5

<?php
$i=20;
while ($i+=20) {
    for ($j=19;$j!==10;--$j){
        if ($i%$j) continue 2;
    }
    die ("result: $i\n");
}

到目前为止，是最快最短的php解决方案。比我的comp上的Czimi快约1.4倍。但请查看python解决方案，这是一个很好的算法。

Answer 6

有些人真的过度思考......

在Ruby中：

puts 5*7*9*11*13*16*17*19

Answer 7

@People做简单的数学;我不确定这是否是演习的目标。你将学习新的语言和新的方法来执行东西。用计算器做这件事并不是正确的事情。

我知道这是旧帖子中的帖子，但它仍然出现在谷歌搜索结果中：）

在代码中执行此操作（即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次

Answer 8

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

它并不像我能做到的那么优雅，但它计算的数字从。到15的2到2000之间的最小公倍数。如果你的迭代解决方案每秒可以处理10亿个候选人，则需要10 ^ 849年才能完成。

换句话说，不要打扰优化错误的算法。