代码之家 › 专栏 › 技术社区 › rg88

一个项目Euler难题(特别是在PHP中)

puzzle math php

-1

rg88 · 技术社区 · 16 年前

最近还有一个ProjectEuler问题,但我认为这有点具体(我只对基于PHP的解决方案感兴趣),所以无论如何我都会问。

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

8 回复 | 直到 9 年前

Czimi 16 年前

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

?>

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

C. K. Young 16 年前

收集1到20之间所有数字的基本因子。计算每个素因子的最大指数,我们有 16 = 2**4 , 9 = 3**2 以及5、7、11、13、17、19(每个仅出现一次)。增加抽签,你就有了答案。

Jamie 16 年前

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

一般来说,如果你想要一个最小的数,它可以被1到n之间的所有数平均整除,你需要找到2到n之间的所有素数,对于每个素数,找到它将范围内任何数相除的最大次数。这可以通过求不大于n的素数的最大幂来计算。

克里斯指出,在20的情况下,2^4是2不大于20的最大幂,3^2是3不大于20的最大幂,对于所有其他素数,只有第一幂不大于20。

Christian C. Salvadó 16 年前

您可以删除一些被除的数字,例如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();
?>

rune_kg 15 年前

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

是目前最快、最短的PHP解决方案。比我的比赛快1.4倍。但是看看python的解决方案,这是一个很好的算法。

Anthony Sinnott 15 年前

有些人真的对这件事想得太多了…

露比:

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

Tjirp 13 年前

@做简单数学的人;我不确定这是否是练习的目的。你要学习新的语言和新的表演方式。仅仅用计算器来计算是不正确的。

我知道这是一篇旧文章,但它仍然出现在谷歌的搜索结果中。

在代码(即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倍的循环

-1

Kirk Strauser 16 年前

我知道你说的是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年才能完成。

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