求 python 中前 1000 个素数的总和

Question

我写了一个程序，计算素数和直到1000。程序如下：

limit = 1000

def is_prime(n):
    for i in range(2, n):
        if n%i == 0:
            return False
    return True

sum = 0
for i in range(2, int(limit+1)):
    if is_prime(i):
        sum = sum + i
        count += 1
print sum

要找到 1000 个素数而不是最多 1000 个数字，我可以做哪些更改？此外，我正在寻找 space 复杂度为 O(1) 和时间复杂度为 O(n) （据我所知，其他方法可以做到 :-) 例如 "Sieve of Eratosthenes" 并在迭代时寻找素数平方根（n）http://www.geeksforgeeks.org/print-all-prime-factors-of-a-given-number/）

如果我哪里出错了，请指正。谢谢。

Answer 1

完成您所要求的最简单方法可能是 itertools。

def gen_primes():
    for i in itertools.count(2):
        if is_prime(i):
            yield i 

first_one_thousand = list(itertools.islice(gen_primes(), 1000))

射，大家都喜欢单线：

first_one_thousand = list(itertools.islice((i for i in itertools.count(2) 
                                            if is_prime(i)), 
                                           1000))

Answer 2

代码：

def f():
    i = 2
    while True:
        if all(i % x != 0 for x in range(2, i-1)):
            yield i
        i += 1

primes = f()
print sum(primes.next() for _ in range(1000))

或者一个班轮：

import itertools
print sum(itertools.islice(itertools.ifilter(lambda x: all(x % i != 0 for i in range(2, x)), f()), 0, 1000))

Answer 3

只是根据您的代码进行了一些小的改进，以找到 limit 个素数而不是 limit 个数字。

limit = 1000

def is_prime(n):
    for i in range(2, n):
        if n%i == 0:
            return False
    return True

sum = 0
num = 2
for i in xrange(limit):
    while not is_prime(num):
        num += 1
    sum += num
    num += 1 # sorry, miss this
print sum

您也可以在查找您感兴趣的特定数量的内容时使用单个循环，这可能只是个人喜好问题。

limit = 1000

def is_prime(n):
    for i in range(2, n):
        if n%i == 0:
            return False
    return True

sum = 0
count = 0
num = 2
while count != limit:
    if is_prime(num):
        sum += num
        count += 1
    num += 1

print sum

Answer 4

我想提出以下算法（埃拉托色尼筛法）

n=1000
limit_sieve = 10000
primes = set()
notPrimes = set()
i = 2
while len(primes)<n:
  if not i in notPrimes:
    primes.add(i);
    for notPrime in range(i*2, limit_sieve, i):
      notPrimes.add(notPrime)
  i+=1

sum(primes)

求 python 中前 1000 个素数的总和

Find sum of first 1000 prime numbers in python

python

algorithm

primes

data-structures