2

これの出力が次のように出力される理由がわかりません。

>  File "<pyshell#177>", line 6, in func
>     list.append(next(PrimeGen)) 
>  StopIteration

それが私の頭の中でとても理にかなっているとき！とにかく基本的に私はリストに素数を集めるためにifprime関数とジェネレーターを使って素数ジェネレーターを作ろうとしています。

これにより、プライムかどうかが判別され、プライムの場合は値が返され、そうでない場合は何も返されません。

def prime(x):
    if (2**(x-1))%x ==1:
        return x

これにより、xまでの素数でいっぱいのリストを返すジェネレータが作成されますが、代わりに上記のエラーが発生します。上記の関数prime（x）は2を素数と見なさないため、リストを2で開始しました（したがって、範囲は3から始まります）

def func(x):
  count=0
  list=[2]
  PrimeGen = (prime(X) for X in range(3,x+1))
  while count<99:
      list.append(next(PrimeGen))
      count+=1
  print list

なぜそれが機能しないのか誰かが説明できますか？前もって感謝します！V。

4

3 に答える 3

5

生成された値は99未満でした。itertools.islice()ループの代わりに使用します。

于 2012-08-01T19:38:07.843 に答える
3

あなたのプライムテストに注意してください

def prime(x):
    if (2**(x-1))%x ==1:
        return x

間違っています、それはeg341 = 11*31と2047 = 23*89primeを宣言します。

また、x非常に大きな中間値を生成するより大きな場合、はるかに効率的です

pow(2,x-1,x)

それは中間値を減らします。

より強力な素数性チェックの適度に効率的な実装：

# The primes below 200 used as bases for the strong Fermat test,
# prime bases have more discriminatory power than composite bases,
# therefore we use prime bases first
bases = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199]

# The strong Fermat test for base b, where n is odd and large,
# n - 1 = m * 2^s with odd m
# the strong test checks whether b**m % n == 1 or
# b**(2**j) % n == n-1 for a 0 <= j < s
# If the test returns False, n is definitely composite, otherwise probably prime
def strongFermat(b,n,m,s):
    a = pow(b,m,n)
    if a == 1:
        return True
    n1 = n-1
    for i in xrange(s):
        if a == n1:
            return True
        a = (a*a) % n
    return False

# Multiple strong Fermat tests, by default use 10 bases
# The probability that a composite passes is less than 0.25**iters
def sppTest(n, iters = 10):
    # Assumes n > 1 and with no prime divisors < 200
    m = n-1
    s = 0
    while (m & 1) == 0:
        m >>= 1
        s += 1
    pbases = iters if iters < 47 else 46
    for i in xrange(pbases):
        if not strongFermat(bases[i],n,m,s):
            return False
    if pbases < iters:
        for i in xrange(iters-pbases):
            if not strongFermat(211 + 2*i,n,m,s):
                return False
    return True

# Trial division to weed out most composites fast
def trialDivisionPrime(n):
    if n < 2:
        return 0        # Not a prime
    if n < 4:
        return 2        # definitely prime
    if n % 2 == 0 or n % 3 == 0:
        return 0        # definitely composite
    for d in xrange(5, 200, 6):
        if d*d > n:
            return 2    # definitely prime
        if n % d == 0 or n % (d+2) == 0:
            return 0    # composite
    return 1            # not yet decided

# The prime test, first do trial division by numbers < 200,
# if that doesn't decide the matter, use some strong Fermat tests
# using 20 tests is the paranoid setting for largish numbers,
# for numbers in 64-bit range, ten or fewer suffice
def prime(n):
    td = trialDivisionPrime(n)
    return td > 1 or (td == 1 and sppTest(n,20))

# just check a couple of larger numbers
for c in xrange(100000):
    if prime(c + 10**25):
        print c
于 2012-08-01T19:43:34.367 に答える
1

これは少し良いです（「素数」関数が素数であるかどうかにかかわらず、数値を返すのはちょっとばかげているようですが、None実際には、以下のわずかに変更されたバージョンの代わりにうまく機能しますbool(None) == False）。結果として次のようになりますStopIteration。

def isprime(x):
    return (2**(x-1))%x==1

def func(x):
    list=[2]
    list.extend(X for X in range(3,x+1) if isprime(X))
    print list

しかし、ダニエル・フィッシャーが述べたことによると、とにかくあなたの主な機能は正しくありません。

于 2012-08-01T19:48:18.130 に答える