0

私はPythonでエラトステネスのふるいの実装を作成しています。発生する問題は、すべての素数（主に小さい番号の素数）が表示されるわけではありません。

これが私のコードです：

def prevPrimes(n):
    from math import sqrt
    from time import time
    start = time()
    if type(n) != int and type(n) != long:
        raise TypeError("Arg (n) must be of <type 'int'> or <type 'long'>")
    if n <= 2:
        raise ValueError("Arg (n) must be at least 2")
    limit, x, num, primes = sqrt(n), 2, {}, []
    for i in range(1, n+1):
        num[i] = True
    while x < limit:
        for i in num:
            if i%x==0:
                num[i] = False
        x += 1
    for i in num:
        if num[i]:
            primes.append(i)
    end = time()
    primes = sorted(primes)
    print round((end - start), 2), ' seconds'
    return primes

を入力>>> prevPrimes(1000)すると、結果は次のようになります。[2, 3, 5, 7, 11, 13, 17]など。ただし、次のようになります[1, 37, 41, 43, 47, #more numbers]。

False私のプログラムが素数をチェックする方法のために、問題は「元の」素数（2、3、5、7、11、13、17など）を示しているという事実にあることを私は知っています。どうすればこれを回避できますか？前もって感謝します ：）

4

4 に答える 4

1

を繰り返すとnum、xはに等しくi、したがってi % x0に等しくなりi、非プライムとしてマークされることがあります。

if not x == i:whileループのどこかに追加する必要があります。例：

while x < limit:
        for i in num:
            if not x == i:
                if num[i] and i%x==0:
                    num[i] = False
于 2012-11-21T05:36:53.130 に答える
1

これは実際のSoE実装ではなかったので、少し前に書いたものを以下に示します。

number_primes = 10
prime_list = [True]*number_primes

for i in range (2, number_primes):    #check from 2 upwards
  if prime_list[i]:                   #If not prime, don't need to bother about searching
    j = 2
    while j*i < number_primes:        # Filter out all factors of i (2...n * prime)
      prime_list[j*i] = False
      j+=1
于 2012-11-21T06:54:57.297 に答える
1

まず、あなたの特定の質問への答え。nの平方根よりも小さい素数を破棄しています。最も簡単な修正は、行num[i] = Falseをnum[i] = (not x == i)内側のループの最後に変更することです（これは機能すると思いますが、テストしていません）。

次に、アルゴリズムは試行除算であり、エラトステネスのふるいではなく、O（n log log n）ではなく時間計算量O（n ^ 2）になります。モジュロ演算子はゲームを放棄します。エラトステネスの最も単純なふるいは次のようになります（疑似コード、Pythonに変換できます）：

function primes(n)
  sieve := makeArray(2..n, True)
  for p from 2 to n step 1
    output p
    for i from p+p to n step p
      sieve[i] := False

そのアルゴリズムを改善する方法があります。素数を使ったプログラミングに興味がある場合は、Pythonで実装された最適化されたエラトステネスのふるいを含むこのエッセイを控えめにお勧めします。

于 2012-11-21T15:24:56.030 に答える
0

インポート時間

def primes_sieve1（）：

limitn = int(raw_input("Please enter an upper limit ")) +1
start = time.clock()
primes = {
    }

for i in range(2, limitn):
    primes[i] = True

for i in primes:
    factors = range(i,limitn, i)
    for f in factors[1:]:
        primes[f] = False

end = time.clock()
print "This took ",end-start," seconds"
return [i for i in primes if primes[i]==True]

primes_sieve1（）

除算を使用する代わりに、このコードは制限のルートよりも小さいすべての数値の倍数を取り、それらをfalseに変更します。すべての数値を他の数値で除算する必要がないため、これはやや高速です。

また、1000未満では、プライムがそれ自体でモジュロされて0になる状況が発生するため、プログラムはそれが偽であると見なします。sqrt（1000）はおよそ31であるため、31未満の素数が影響を受けます。

たとえば、「while x <limit」の7番目のループでは、次のような状況が発生します。7％7 == 0であるため、プログラムでは7がfalseのように見えます。これは、「while x <limit」ループの制限未満のすべての素数で発生します。これは、ある時点でxが検索しようとしている素数になるためです。

于 2015-02-18T16:49:14.440 に答える