0

別の最近の Project Euler に関する質問がありますが、これはもう少し具体的なものだと思います (私は PHP ベースのソリューションにしか本当に興味がないので) とにかく質問します。

質問 #5は、「1 から 20 までのすべての数で割り切れる最小の数は?」という課題です。

今、私はそれを2回解決しました。かつては非常に非効率的で、かつてははるかに効率的でしたが、特に洗練された答えにはまだほど遠いです（そして、私は数学が特にしっかりしていないため、力ずくの解決策です）。これを改善できる領域がいくつかありますが、この問題に対するより効率的な解決策を示すことができる人がいるかどうか疑問に思っています.

*スポイラー: これは私の最適ではありませんが (実行に 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 までのすべての数の素因数を集めます。各素因数の最大指数を数えると、 、 、および 5、7、11、13、17、19 16 = 2**4(9 = 3**2それぞれが 1 回しか現れません) があります。くじを掛けると、答えが得られます。

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

?>

あなたが投稿したものよりも少なくとも2倍高速です。

于 2008-10-11T01:37:24.247 に答える
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 に答える
2

クリス・ジェスター・ヤングは正しい。

一般に、1 から N までのすべての数で割り切れる最小の数が必要な場合は、2 から N までのすべての素数を見つけ、それぞれについて、それが任意の数を割り切れる最大の回数を見つけたいと思うでしょう。範囲内の数。これは、N 以下の素数の最大べき乗を求めることで計算できます。

Chris が指摘したように、20 の場合、2^4 は 20 を超えない 2 の最大のべき乗であり、3^2 は 20 を超えない 3 の最大のべき乗であり、他のすべての素数については最初のべき乗のみです。は 20 以下です。

于 2008-10-11T01:14:50.720 に答える
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

@簡単な計算をしている人々。それが練習の目標かどうかはわかりません。あなたは新しい言語と物事を行うための新しい方法を学ばなければなりません. 電卓で計算するだけでは、正しい方法ではありません。

そして、これが古い古いスレッドの投稿であることは知っていますが、それでもGoogleの結果に表示されます:)

コード（つまり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 であると既に述べられているためです。したがって、20 ではなく 2520 だけインクリメントできます。その結果、ループが 126 分の 1 になります。

于 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)

私が作成したほどエレガントではありませんが、2 から 2000 までの数値の最小公倍数を .15 秒で計算します。反復ソリューションが 1 秒あたり 10 億の候補を処理できる場合、完了するまでに 10^849 年かかります。

つまり、間違ったアルゴリズムを最適化する必要はありません。

于 2008-10-11T05:00:02.560 に答える