计算函数的输出 python

Question

我正在使用以下代码来测试素数。

def primes(n):
    """ Returns  a list of primes < n """
    sieve = [True] * n
    for i in xrange(3,int(n**0.5)+1,2):
        if sieve[i]:
            sieve[i*i::2*i]=[False]*((n-i*i-1)/(2*i)+1)
    yield [2] + [i for i in xrange(3,n,2) if sieve[i]]


outfile = open('primes','w')
input = input("Feed Me:")

outfile.write(str(primes(input)))
print "Done"

有没有一种简单的方法来计算生成的素数。而不是打印实际数字？也可以使此代码生成大于 100000000 的素数而不会溢出吗？

Answer 1

您可以删除 table 中的每个偶数，只需将整数除以 2 即可仅存储奇数。 sum 使用布尔值将它们映射到整数：True 是 1，False 是 0；请注意，对于 n >= 2，即使 table 中没有 2 也可以工作，因为 1 在 table 中被标记为素数 ;)

def n_primes(n):
    """ Returns  the number of primes < n """
    sieve = [True] * (n//2)
    for i in xrange(3,int(n**0.5) + 1,2):
        if sieve[i//2]:
            sieve[i*i//2::i]=[False]*((n-i*i-1)/(2*i)+1)

    return sum(sieve)

甚至更好，计算遇到的素数：

def n_primes(n):
    """ Returns  the number of primes < n (for n > 2)"""
    n_p = 1  # 2 is a prime
    sieve = [True] * (n//2)
    for i in xrange(3,int(n**0.5) + 1,2):
        if sieve[i//2]:
            n_p += 1
            sieve[i*i//2::i]=[False]*((n-i*i-1)/(2*i)+1)

    return n_p

请注意，您的 sieve 函数不是 return 列表而是一个产生结果的生成器，您可能想将原始代码编写为

def primes(n):
    """ Returns  a list of primes < n """
    sieve = [True] * n
    for i in xrange(3,int(n**0.5)+1,2):
        if sieve[i]:
            sieve[i*i::2*i]=[False]*((n-i*i-1)/(2*i)+1)

    return [2] + [i for i in xrange(3,n,2) if sieve[i]]

或使用我的生成器版本：

def primes(n):
    """ Yields a sequence of primes < n """
    if n <= 2:
        return

    yield 2
    sieve = [True] * (n//2)
    for i in xrange(3,int(n**0.5) + 1,2):
        if sieve[i//2]:
            yield i
            sieve[i*i//2::i] = [False] * ((n-i*i-1)/(2*i)+1)

在第一种情况下，您可以执行 len(primes(n)) 来获取号码（尽管这很浪费），对于第二种情况，您可以执行 sum(1 for i in primes(n))

至于生成高于 100000000 的质数，sieve table 将在 32 位处理器上花费 (4 * n / 2) 个字节，在 64 位处理器上花费 8 * n / 2 个字节位处理器，所以你的里程可能会有所不同......人们会想要使用某种 bitarray 尽管其中一种不是内置的 python.

计算函数的输出 python

count output of a function python

python

math

memory-management