[已解决]如何优化素数生成器求和

亘川锌酸猫

刚开始学零基础python，做生成器课后作业，代码可以正确计算2,000,000以内所有素数的和，但是用时极长，运行了500多秒，非常没有效率。
目测是因为随着找到素数的数量增加，计算量也指数上涨。

要怎么改进才能提升效率？还是说这种计算方法本身就过于繁琐，不适合用来生成素数？

代码：

def prime_seq():
    prime_list = [2, 3]
    yield 2
    yield 3
    i = 3
    while True:
        i += 2
        for each_prime in prime_list:
            if i % each_prime == 0:
                break
        else:
            prime_list.append(i)
            yield i


sum_of_primes = 0
# 这里用一个计时器简单记录跑代码的时间
start_time = time.time()
for each in prime_seq():
    if each < 2000000:
        sum_of_primes += each
    else:
        print(sum_of_primes)
        end_time = time.time()
        print('Run time: %.4f' %(end_time - start_time))
        break

最佳答案

月排行榜 / 总排行榜

TJBEST

2020-4-6 17:29:25

你看看这结果对吗？

import time
def SieveOfEratosthenes(n): 
    prime = [True for i in range(n+1)] 
    p = 2
    while p * p <= n: 
        if (prime[p] == True): 
            for i in range(p * 2, n + 1, p): 
                prime[i] = False
        p += 1
    for index in range(2,n+1):
        if prime[index]:
            yield index
def prime_seq():
    return SieveOfEratosthenes(2005000)
sum_of_primes = 0
# 这里用一个计时器简单记录跑代码的时间
start_time = time.time()
for each in prime_seq():
    if each < 2000000:
        sum_of_primes += each
    else:
        print(sum_of_primes)
        end_time = time.time()
        print('Run time: %.4f' %(end_time - start_time))
        break

跳转到最佳答案楼层

BngThea

用sum函数一次性求和

亘川锌酸猫

BngThea 发表于 2020-4-6 14:43
用sum函数一次性求和

刚去尝试了一下，并没有变快。我怀疑是生成器不够优化的问题。

TJBEST

你的素数求法不是最优解，我给你一个方法，保证提高速度，17:30奉上答案，及得采纳哦，好了我去写了

zltzlt

不知道这个够不够快

import time


def is_prime(n):
    return True if n in {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67} else all(
        False for p in {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67} if
        pow(p, n - 1, n) != 1)


def prime_seq():
    yield 2
    yield 3
    i = 3
    while True:
        i += 2
        if is_prime(i):
            yield i


sum_of_primes = 0
# 这里用一个计时器简单记录跑代码的时间
start_time = time.time()
for each in prime_seq():
    if each < 2000000:
        sum_of_primes += each
    else:
        print(sum_of_primes)
        end_time = time.time()
        print('Run time: %.4f' % (end_time - start_time))
        break

永恒的蓝色梦想

def func(end):
    primelist=[True]*(end+1)
    primelist[0]=primelist[1]=False
    for i,prime in enumerate(primelist[:end>>1]):
        if prime:
            for j in range(2*i,end+1,i):
                primelist[j]=False
    return sum((i for i,prime in enumerate(primelist) if prime))

print(func(2000000))

素数筛法

TJBEST

你看看这结果对吗？

import time
def SieveOfEratosthenes(n): 
    prime = [True for i in range(n+1)] 
    p = 2
    while p * p <= n: 
        if (prime[p] == True): 
            for i in range(p * 2, n + 1, p): 
                prime[i] = False
        p += 1
    for index in range(2,n+1):
        if prime[index]:
            yield index
def prime_seq():
    return SieveOfEratosthenes(2005000)
sum_of_primes = 0
# 这里用一个计时器简单记录跑代码的时间
start_time = time.time()
for each in prime_seq():
    if each < 2000000:
        sum_of_primes += each
    else:
        print(sum_of_primes)
        end_time = time.time()
        print('Run time: %.4f' %(end_time - start_time))
        break

TJBEST

好吧，你要的是生成器，我可以改成一个无限素数的生成器，稍等。

亘川锌酸猫

TJBEST 发表于 2020-4-6 17:29
你看看这结果对吗？

感谢帮助，容我慢慢品一品

亘川锌酸猫

永恒的蓝色梦想 发表于 2020-4-6 17:25
素数筛法

感谢！容我理解学习一下

TJBEST

亘川锌酸猫 发表于 2020-4-6 17:39
感谢帮助，容我慢慢品一品

我觉得这个更符合你的要求。可以无限输出，手动break
核心思想 假设：一个正整数n>4 且 正整数m满足2<m < n 。命题' m是合数' 等价于命题'存在一个质数p，满足 p <=根号（n）能够整除m'

import math
import time
def prime_seq(): 
    prime = [True for i in range(1000000 + 1)] 
    jilu = set()
    p = 2
    #第一次遍历
    while p * p <= 1000000: 
        if (prime[p] == True): 
            for i in range(p * 2, 1000000 + 1, p): 
                prime[i] = False
        p += 1
    for index in range(2,1000000+1):
        if prime[index]:
            jilu.add(index)
            yield index
    prime = [True for i in range(1000000)] 
    page = 1
    while True:
        offset = 1000000*page + 1
        end = 1000000 * (page + 1)
        #第page+1次遍历
        firstGate = math.floor(end**(1/2))
        for p  in jilu :
            if p > firstGate:
                continue
            firstRes = offset % p
            fisrtPosition = (p - firstRes)%p
            for i in range(fisrtPosition,1000000,p):
                prime[i] = False
        for index in range(0,1000000):
            if prime[index]:
                jilu.add(offset + index)
                yield offset + index
        page += 1
        prime = [True for i in range(1000000)] 
sum_of_primes = 0
# 这里用一个计时器简单记录跑代码的时间
start_time = time.time()
for each in prime_seq():
    if each < 2000000:
        sum_of_primes += each
    else:
        print(sum_of_primes)
        end_time = time.time()
        print('Run time: %.4f' %(end_time - start_time))
        break