2

我有这两个功能一起工作。第一个生成下一个素数。第二个将该素数附加到素数列表中。当我基本上说 i = next(n) = nextPrime(primeList) 时,我觉得我在第二个函数中过度使用了变量。有没有更好的方法来写这个?

def nextPrime(primeList):
    checkNum = 3
    while True:
        for i in primeList:
            if checkNum % i == 0:
                break
            if i > math.sqrt(checkNum):
                yield checkNum
                break
        checkNum += 2


def primeNumbers(limit):
    primeList = [2]
    i = 0
    n = nextPrime(primeList)
    while i <= limit:
        i = next(n)
        primeList.append(i)
    return primeList

primeList = primeNumbers(200000)
4

3 回答 3

2

这行得通吗?

def primeNumbers(limit):
    primeList = [2]
    for i in nextPrime(primeList):
        if i > limit:
            break
        primeList.append(i)
    return primeList
于 2013-02-11T21:43:49.570 回答
2

您可以使用itertools.takewhile为您完成大部分工作:

import itertools

def primeNumbers(limit):
    primes = nextPrime((2,))

    # Limit to `limit`.
    primes = itertools.takewhile(lambda i: i <= limit, primes)

    # Return a list.
    return list(primes)
于 2013-02-11T21:51:04.663 回答
1

这不使用两个函数来做到这一点,但这是使用Eratosthenes 的 Sieve生成​​最高为 'n' 的素数的一般(我相信是最快的)方法:

def prevPrimes(n):
    """Generates a list of primes up to 'n'"""
    from numbers import Integral as types #'Integral' is a class of integers/long-numbers
    if not isinstance(n, types): raise TypeError("n must be int, not " + str(type(n)))
    if n < 2: raise ValueError("n must greater than 2")
    primes_dict = {i : True for i in range(2, n + 1)} # initializes the dictionary
    for i in primes_dict:
        if primes_dict[i]: #avoids going through multiples of numbers already declared False
            num = 2
            while (num * i <= n): #sets all multiples of i (up to n) as False
                primes_dict[num*i] = False
                num += 1
    return [num for num in primes_dict if primes_dict[num]]

正如 Jack J 所指出的,避免使用所有偶数会使这段代码更快。

def primes(n):
    """Generates a list of primes up to 'n'"""
    primes_dict = {i : True for i in range(3, n + 1, 2)} # this does not
    for i in primes_dict:
        if primes_dict[i]:
            num = 3
            while (num * i <= n):
                primes_dict[num*i] = False
                num += 2
    primes_dict[2] = True
    return [num for num in primes_dict if primes_dict[num]]

然后运行测试:

from timeit import timeit
def test1():
    return primes(1000)

print 'Without Evens: ', timeit(test1, number=1000)
print 'With Evens: ', timeit(stmt='prevPrimes(1000)', setup='from nums import prevPrimes', number=1000)

输出:

>>> 
Without Evens:  1.22693896972
With Evens:  3.01304618635
于 2013-02-11T21:54:43.367 回答