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 的素数的列表，但却给出了上面的错误。我以 2 开始列表，因为上面的函数 prime(x) 不将 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

谁能解释为什么它不起作用？先感谢您！五。

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）并且没有t导致你得到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

但是按照 Daniel Fischer 的说法，你的主要功能无论如何都是不正确的。

于 2012-08-01T19:48:18.130 回答