sieve-of-eratosthenes - エラトステネスの篩における関数の反転

Question

これは技術的には車輪の因数分解だと思います。プログラムのエラトステネスの篩の表現を再圧縮しようとしています。これには、素数である可能性のある数値のインデックスのみが含まれています。

背景:

最も基本的なホイールは [2] です: 最初の素数として 2 を追跡し、ふるいには奇数インデックスのみが含まれます。(50%))

次のホイールは [2 3] です: 最初の素数として 2 と 3 を追跡し、ふるいには 2*3=6 (つまり、1 と 5) の間のギャップのみが含まれます。インデックスの形式は 6k+1 および 6k+5 です。(33%)

次のホイールは [2 3 5] です: 最初の素数として 2、3、および 5 を追跡し、サイズ 30 の間隔を表すためにふるいに必要なのは 8 ビットのみです。 (27%)

数値の倍数のビットをクリアするとき、次のループを使用してそれらの倍数を見つけます。

def multiplesIndices (self, i):
    for gap in self.gaps[1:]:
        ret = i * (self.product * 0 + gap)
        if ret > len (self): break
            yield ret
    for k in xrange (1, len (self) / i / self.product + 1):
        for gap in self.gaps:
            ret = i * (self.product * k + gap)
            if ret > len (self): break
            yield ret

問題は、ホイールのセットアップにかかる時間と、圧縮比の収穫逓減です。それと rn を別のホイール サイズに変更するには、多くの再計算が必要です。また、ホイールのサイズを変えることで、漸近的な複雑さに影響を与えることができると思います。

したがって、私の提案する解決策は、小さなホイールを使用して大きなホイールを初期化することです。 [2 3 5 7] (210/48) ホイール

助けが必要なのは、計算済みの小さなふるいを、これから計算される大きなふるいにマッピングすることです。これにより、すべてを 1 から再ふるい分けすることを避けることができます。最初の 30 個の素数を取得し、それらを使用して次の 210 ～ 30 個の素数を見つけます。それらを使用して、次の 480-210 素数を見つけます。

より具体的には、この関数を反転する (または invIndexOf() を正しく実装する) 助けが必要です。

def indexOf (self, n):
    if not self.isValidIndex (n): raise Exception ()
    ret = n / self.product * len (self.gaps) + self.gaps.index (n % self.product)
    assert n in self.invIndexOf (ret)
    return ret

また、何かの漸近的な複雑さを理解してから数年が経ちました。劇的な改善ではありませんが、これは改善であると確信しています。