エラトステネスのふるい: 「クロスオーバー」ステップの加速

php Xiaobian Apple は、素数をすばやく計算するためのアルゴリズムであるエラトステネスのふるいを紹介します。このアルゴリズムは、非素数の倍数を継続的に除外することにより、すべての素数を除外します。素数を 1 つずつ判断する従来の方法と比較して、エラトステネスのふるい法は計算プロセスを大幅に高速化できます。その中心的なアイデアは、2 から n まで走査し、走査が完了するまで素数 p の各倍数を非素数としてマークすることです。この方法は、多数の素数を計算する場合に優れたパフォーマンスを発揮し、効率的な素数計算アルゴリズムです。

質問内容

エラトステネスのふるいアルゴリズムを使って素数を列挙する関数を以下のように実装しました。 リーリー

しかし、非効率であることがわかりました。つまり、

CrossOffMultiples が必要以上に呼び出されました。 IOW、「取り消し線」が引かれた整数は、2 回または 3 回 (またはそれ以上) 取り消し線が引かれます。これは、複数の m を分割する複数の要素があるためです。しかし、この情報を活用して CrossOffMultiples への呼び出し数を減らす方法がわかりません。これを行う方法があると確信していますが、何らかの理由でそれができません。 ＃＃＃助言がありますか？

回避策

CrossOffMultiples

の呼び出し回数を減らす、つまり一部の素数pで呼び出さない場合は、 p * p は取り消されません。ただし、できることは、2 * p ではなく p * p からループを開始することです。 数字に複数回取り消し線を引くのは普通のことであり、これがエラトステネスのふるいでした。

Linear Sieve Method

も同様のアルゴリズムで、興味があるかもしれません。

以上がエラトステネスのふるい: 「クロスオーバー」ステップの加速の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。