2

一緒に機能するこれら2つの機能があります。最初は次の素数を生成します。2 番目は、その素数を素数のリストに追加します。基本的に i = next(n) = nextPrime(primeList) と言うと、2 番目の関数で変数を使いすぎているように感じます。これを書く良い方法はありますか？

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

これはそれを行うために2つの関数を使用しませんが、エラトステネスのふるいを使用して「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 に答える