0

私はいくつかの検索を行いましたが、この実装と私が見た他のすべての実装に関する情報を見つけることができませんでした.

function sieve($top)
{
    for($i = 11; $i<$top; $i+=2)
    {
         if($i % 3 == 0 || $i % 5 == 0 
            ||  $i % 7 == 0)
          {
             continue;
          }
       echo "$i <br />";
   }
}

ええ、私はそれを印刷するだけだと知っていますが、それは重要な部分ではありません. それが時間であろうとなかろうと、主な落とし穴は何ですか?

編集: スケーラビリティ以外の問題はありますか? また、主要な発見を進めることについてのコメントにも感謝します。

4

5 に答える 5

4

これの主な落とし穴は、スケーリングしないことです。数値が十分に大きくなると、何でも返されます。モジュラス エクスクルーダーのリストは、検索とともに拡大する必要があります。

于 2009-12-07T17:42:52.767 に答える
1

ウィキペディアでエラトステネスのふるいを参照できます。PHP実装のこのリンク。

于 2009-12-07T18:02:58.723 に答える
0

まず、3つの数値（3、7、および11）に対してのみチェックします。エラトステネスのふるいについては、番号のリスト2..iから始める必要があります。次に、そのリストをループして、繰り返し処理している数値の要因である数値を削除します。たとえば、素数である7に到達したら、49、56、およびその他の7の倍数を削除する必要があります。

次に、今説明した方法ではスケーリングが非常に不十分です。1..10^ 9から素数を検索しようとした場合、リストに10^9の値が必要になります。エラトステネスのふるい以外にも素数を見つける方法があります-http ://en.wikipedia.org/wiki/Prime_numberを参照してください

于 2009-12-07T18:12:51.967 に答える
0

この機能は「エラトステネスアルゴリズムのふるい」を使用しています

function getPrimaryNumbers($n)
{
    $sieve = [];
    for($i = 1; $i <= $n; $i++) {
        $sieve[$i] = $i;
    } 

    $i =2;
    while($i * $i <= $n) {      
        if(isset($sieve[$i])) {
            $k = $i;
            while ($k * $i <= $n) {         
                unset($sieve[$k * $i]);
                $k++;
            }   
        }
    $i++;
    }           
    return $sieve;
}
于 2015-10-07T15:26:10.120 に答える
0

11までの素数に制限されています。さらに拡張するには、|| $u % 11 == 0 || $i % 13 == 0 ...などを追加する必要があります

于 2009-12-07T17:43:02.967 に答える