3

私のSieveofAtkinの実装では、限界近くの素数または限界近くのコンポジットを見落としています。一部の制限は機能し、他の制限は機能しません。私は何が悪いのか完全に混乱しています。

def AtkinSieve (limit):
results = [2,3,5]
sieve = [False]*limit
factor = int(math.sqrt(lim))
for i in range(1,factor):
    for j in range(1, factor):
        n = 4*i**2+j**2
        if (n <= lim) and (n % 12 == 1 or n % 12 == 5):
            sieve[n] = not sieve[n]
        n = 3*i**2+j**2
        if (n <= lim) and (n % 12 == 7):
            sieve[n] = not sieve[n]
        if i>j:
            n = 3*i**2-j**2
            if (n <= lim) and (n % 12 == 11):
                sieve[n] = not sieve[n]
for index in range(5,factor):
    if sieve[index]:
        for jndex in range(index**2, limit, index**2):
            sieve[jndex] = False
for index in range(7,limit):
    if sieve[index]:
        results.append(index)
return results

たとえば、1000の制限まで素数を生成すると、アトキンのふるいは素数997を見逃しますが、複合965を含みます。しかし5000の制限まで生成すると、返されるリストは完全に正しいです。

4

1 に答える 1

6

  • に変更limしlimitます。もちろん、あなたはそれを知っていたに違いありません。
  • 以来sieve = [False]*limit、許可される最大のインデックスはですlimit-1。

    ただし、この行では

    if (n <= limit) and (n % 12 == 1 or n % 12 == 5):

    かどうかを確認していますn<=limit。n==limitその後sieve[n]、IndexErrorが発生します。の値を小さくしてアルゴリズムを試してくださいlimit（例：n = 50）。このエラーが表示されます。簡単な修正は使用することです

    sieve = [False]*(limit+1)

    sieve [0]は使用されないため、簡単な修正は少し無駄です。したがって、より良い修正は保持することだと思うかもしれませんがsieve = [False]*limit、インデックスをsieve1つ下げることによって、他のすべてのコードを修正します。（たとえば、どこにでも変更sieve[n]するsieve[n-1]など）ただし、これにより、速度に適さないいくつかの追加の減算を実行する必要があります。したがって、簡単で無駄な解決策は、実際にはおそらくより良い選択肢です。

  • http://en.wikipedia.org/wiki/Sieve_of_Atkinによると、xはエンドポイントを含む[1、sqrt（limit）]の整数である必要があります。

    あなたのコードで

    factor = int(math.sqrt(limit))

    の床をint取ります。さらに、math.sqrt(limit)

    range(1,factor)1からファクター1になります。だからあなたは1つずれています。

    したがって、これを次のように変更する必要があります

    factor = int(math.sqrt(limit))+1

  • Steve Krenzelによる、Sieve of Atkinの代替（およびより高速な）実装については、 N未満のすべての素数をリストする最速の方法を参照してください。

def AtkinSieve (limit):
    results = [2,3,5]
    sieve = [False]*(limit+1)
    factor = int(math.sqrt(limit))+1
    for i in range(1,factor):
        for j in range(1, factor):
            n = 4*i**2+j**2
            if (n <= limit) and (n % 12 == 1 or n % 12 == 5):
                sieve[n] = not sieve[n]
            n = 3*i**2+j**2
            if (n <= limit) and (n % 12 == 7):
                sieve[n] = not sieve[n]
            if i>j:
                n = 3*i**2-j**2
                if (n <= limit) and (n % 12 == 11):
                    sieve[n] = not sieve[n]
    for index in range(5,factor):
        if sieve[index]:
            for jndex in range(index**2, limit, index**2):
                sieve[jndex] = False
    for index in range(7,limit):
        if sieve[index]:
            results.append(index)
    return results
于 2010-03-08T02:43:56.407 に答える