论坛 › Python交流 › 如何优化素数生成器求和

亘川锌酸猫 发表于 2020-4-6 14:39:17

如何优化素数生成器求和

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

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

代码：
def prime_seq():
    prime_list =
    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

BngThea 发表于 2020-4-6 14:43:29

用sum函数一次性求和

亘川锌酸猫 发表于 2020-4-6 15:06:27

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

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

TJBEST 发表于 2020-4-6 17:01:09

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

zltzlt 发表于 2020-4-6 17:15:43

本帖最后由 zltzlt 于 2020-4-6 17:17 编辑

不知道这个够不够快{:10_256:}

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

永恒的蓝色梦想 发表于 2020-4-6 17:25:49

本帖最后由 永恒的蓝色梦想 于 2020-4-6 17:26 编辑

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

print(func(2000000))素数筛法

TJBEST 发表于 2020-4-6 17:29:25

你看看这结果对吗？
import time
def SieveOfEratosthenes(n):
    prime =
    p = 2
    while p * p <= n:
      if (prime == True):
            for i in range(p * 2, n + 1, p):
                prime = False
      p += 1
    for index in range(2,n+1):
      if prime:
            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 发表于 2020-4-6 17:38:51

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

亘川锌酸猫 发表于 2020-4-6 17:39:30

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

感谢帮助，容我慢慢品一品{:10_257:}

亘川锌酸猫 发表于 2020-4-6 17:40:16

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

感谢！容我理解学习一下{:10_282:}

TJBEST 发表于 2020-4-6 18:28:03

亘川锌酸猫 发表于 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 =
    jilu = set()
    p = 2
    #第一次遍历
    while p * p <= 1000000:
      if (prime == True):
            for i in range(p * 2, 1000000 + 1, p):
                prime = False
      p += 1
    for index in range(2,1000000+1):
      if prime:
            jilu.add(index)
            yield index
    prime =
    page = 1
    while True:
      offset = 1000000*page + 1
      end = 1000000 * (page + 1)
      #第page+1次遍历
      firstGate = math.floor(end**(1/2))
      for pin jilu :
            if p > firstGate:
                continue
            firstRes = offset % p
            fisrtPosition = (p - firstRes)%p
            for i in range(fisrtPosition,1000000,p):
                prime = False
      for index in range(0,1000000):
            if prime:
                jilu.add(offset + index)
                yield offset + index
      page += 1
      prime =
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

查看完整版本: 如何优化素数生成器求和