プロジェクトオイラー||質問10

Question

私はPHPでProject Eulerを解決しようとしていますが、whileループ内のforループ条件で問題が発生しています。誰かが私を正しい方向に向けることができますか？私は正しい道にここにいますか？

問題は、ところで、2,000,000

その他の注意事項以下のすべての素数の合計を見つけることです：私は遭遇しています問題は、メモリ豚のようだということで、ふるいを実装するほかに、私は」他にどのようにこれにアプローチするか分からない。だから、私は実装で何か間違っていたのだろうかと思います。

<?php 

// The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17. 
// Additional information: 
// Sum below 100: 1060 
//  1000: 76127 
// (for testing) 

// Find the sum of all the primes below 2,000,000. 

// First, let's set n = 2 mill or the number we wish to find 
// the primes under. 

$n = 2000000; 

// Then, let's set p = 2, the first prime number. 

$p = 2; 

// Now, let's create a list of all numbers from p to n. 

$list = range($p, $n); 

// Now the loop for Sieve of Eratosthenes. 
// Also, let $i = 0 for a counter. 

$i = 0; 

while($p*$p < $n) 
{ 
// Strike off all multiples of p less than or equal to n 

    for($k=0; $k < $n; $k++) 
    { 
     if($list[$k] % $p == 0) 
     { 
     unset($list[$k]); 
     } 
    } 

// Re-initialize array 

sort ($list); 

// Find first number on list after p. Let that equal p. 

$i = $i + 1; 

$p = $list[$i]; 

} 

echo array_sum($list); 

?> 

Answer 1

私はコードが実行されており、小さな例（17など）を渡しています。しかし、それは8分かかりました。それはまだ私のマシン上で実行されています。私はこのアルゴリズムがシンプルではあるが、多くの数字を何度も実行しなければならないので、最も効果的ではないと思われる。 （最初の実行では200万回のテスト、次のテストでは100万回のテストが行​​われ、一度に削除する回数は少なくなります）また、数百万のリストを格納しているので整数の

これに関係なく、コードの最終コピーが作成され、変更内容のリストとその理由が記載されています。私はそれがまだ200万人のために働いているかどうかはわかりませんが、私たちは見るでしょう。

編集：これは正解です！わーい！

• 設定-1へmemory_limitが、それはこの非常に特殊なケースのために望んでいるとして、PHPで
• （生産スクリプトでは非常に、非常に悪いアイデア！）PHPは、できるだけ多くのメモリを取ることができるようmod
の代わりに %を使用します
• 内部ループと外部ループで同じ変数を使用することはできません。 PHPは同じスコープを持つとみなします。内部ループには$jを使用してください。
• 、内側のループでプライムストライキ自体オフを避ける解除に$i + 1
• で$jを開始するには、あなたが$arr代わりの$listを使用;）
• あなたが未設定の上$を逃したので、PHPは$list[j]を解釈$list['j']となります。ちょうどタイプミス。

私はそれがすべてだと思います。私はいくつかの進捗状況を出して実行しましたが、現在までに到達した最高のプライムは599です。どうすればいいのか教えてください:)

この問題のRubyの私の戦略は、 nは素数であり、2と​​をループしています。これはおそらく最適な解決策ではなく、実行に時間がかかりますが、ほんの1〜2分程度です。それは、アルゴリズム可能性があり、あるいはそれはただのRuby、PHPよりも仕事のこの種では良くあることかもしれない：/

決勝コード：

<?php 

ini_set('memory_limit', -1); 

    // The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17. 
    // Additional information: 
    // Sum below 100: 1060 
    //  1000: 76127 
    // (for testing) 

    // Find the sum of all the primes below 2,000,000. 

    // First, let's set n = 2 mill or the number we wish to find 
    // the primes under. 

    $n = 2000000; 

    // Then, let's set p = 2, the first prime number. 

    $p = 2; 

    // Now, let's create a list of all numbers from p to n. 

    $list = range($p, $n); 

    // Now the loop for Sieve of Eratosthenes. 
    // Also, let $i = 0 for a counter. 

$i = 0; 

while($p*$p < $n) 
    { 
    // Strike off all multiples of p less than or equal to n 

    for($j=$i+1; $j < $n; $j++) 
    { 
    if($list[$j] % $p == 0) 
    { 
     unset($list[$j]); 
    } 
    } 

    // Re-initialize array 

    sort ($list); 

    // Find first number on list after p. Let that equal p. 

    $i = $i + 1; 

    $p = $list[$i]; 
    echo "$i: $p\n"; 
    } 

echo array_sum($list); 

    ?> 

Answer 2

あなたのミドルループに主要な最適化を行うことができます。2 * pで始まり、$ pではなく、1本ずつ増加することにより

for($k=0; $k < $n; $k++) 
    { 
     if($list[$k] % $p == 0) 
     { 
     unset($list[$k]); 
     } 
    } 

は、全繰り返しを減らすだけでなく割り切れるチェックする必要がなくなります。

for($k=2*$p; $k < $n; $k += $p) 
{ 
     if (isset($list[k])) unset($list[$k]); //thanks matchu! 
} 

内側のループは、これらのケースのために地面を降りたことがないので、私はそのこと重要とは思わないが、（2以外）で開始するだけオッズを確認するための上記の提案は、同様に良いアイデアです。私も助けることができませんが、非効率的な、私は100％そのことについては確信していないと考えています。

実際に要素を削除するのではなく、素数に 'ブール値'配列を使用して解決します。私はマップ、フィルター、減らして物事を使用するのが好きですが、私はあなたがやったことの近くにIDスティックを考え出しました、そして、これはとにかく（より長いですが）効率的かもしれません。

$top = 20000000; 
    $plist = array_fill(2,$top,1); 
    for ($a = 2 ; $a <= sqrt($top)+1; $a++) 
    { 
     if ($plist[$a] == 1) 
      for ($b = ($a+$a) ; $b <= $top; $b+=$a) 
      { 
       $plist[$b] = 0; 
      } 
    } 

    $sum = 0; 
    foreach ($plist as $k=>$v) 
    { 
     $sum += $k*$v; 
    } 
    echo $sum; 

私がプロジェクトオイラーのためにこれをしたとき、私はほとんどの場合と同じように、Pythonを使用しました。私が主張したのと同じ行にPHPを使用した人は、7秒（2ページのSekaiAi、見る人のために）を実行したと主張しています。私は実際に彼のフォーム（forループの本体をインクリメント句に入れること）を気にしませんし、グローバルとその機能を使用することもありますが、主なポイントはすべてそこにあります。 PHPをテストする私の便利な手段は、VMWareFusionローカルマシン上のサーバーを介して実行されるので、その速度は遅く、経験から実際にコメントすることはできません。