[已解决]课后联系的疑问

a3522661110 · 发表于 2018-6-3 16:54:30

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

问题：大神，能否写一下你们的解题思路，并给代码注释一下，谢谢了！

1、10以内的素数之和是：2 + 3 + 5 + 7 = 17，那么请编写程序，计算2000000以内的素数这和？
答：如果你的策略是将2000000以内的所有素数找到并存放到一个列表中，再依次进行求和计算，那么这个列表极有可能会撑爆你的内存。
所以，这道题必须用到生成器来实现。
例子：
import math

def is_prime(number):
if number > 1:
      if number == 2:
         return True
      if number % 2 == 0:
         return False
      for current in range(3, int(math.sqrt(number) + 1), 2):
         if number % current == 0:
            return False
      return True
return False

def get_primes(number):
while True:
      if is_prime(number):
         yield number
      number += 1

def solve():
total = 2
for next_prime in get_primes(3):
      if next_prime < 2000000:
         total += next_prime
      else:
         print(total)
         return

if __name__ == '__main__':
solve()

最佳答案

月排行榜 / 总排行榜

simplerjiang

2018-6-3 21:46:55

我写了好鸡儿久，记得给我设置一下最佳答案

import math
def is_prime(number): #判断是否为素数的函数，如果是，返回True,反之返回True
if number > 1: #如果输入的数小于1， 1和0并不是素数
if number == 2: #2是素数，直接返回True
return True
if number % 2 == 0: #number余2等于0就说明不是素数，返回False
return False
for current in range(3, int(math.sqrt(number) + 1), 2): #将3 到根号number 中的所有数，循环放入current
if number % current == 0: #如果3 到根号number 其中任何一个数可以整除number，那它就不是素数
return False
return True #反之如果 3 至根号number 中的所有数都不能整除number，他就是一个素数
return False
def get_primes(number): #这里传入的number，其实是从3开始传入的
while True: #进入无限循环
if is_prime(number): #判断是否number是否为素数
yield number #如果是素数,就返回number, get_primes() 函数在此暂停！注意是暂停不是释放，下次调用的时候会继续从这里开始。
number += 1 #当下一次调用get_primes() 函数时，会执行 number 自加一，然后继续循环。
def solve():
total = 2 #
for next_prime in get_primes(3): #传入3,for .. in .. 关键字会不断调用get_primes() 函数，注意是一遍又一遍的调用，因为我们在get_primes()函数中并没有设置什么时候跳出死循环，所以它会一直生成新的素数
if next_prime < 2000000: #如果输出的素数 next_prime 是小于2000000的，就是我们需要的数，把它加给total
total += next_prime
else: #如果以及超出了2000000，将跳出死循环，不再获取素数
print(total) #打印出2000000以下的所有素数之和.
return #这里返回空值，其实是将return 当作break来使用，跳出这个for循环，因为get_primes() 是一个无限的生成器，所以需要跳出它.
if __name__ == '__main__': #这个代码的意思是如果是本文件运行就运行下列代码
solve()

复制代码

跳转到最佳答案楼层

simplerjiang · 发表于 2018-6-3 21:46:55

这个最佳答案由 simplerjiang 给出，感谢 simplerjiang 的回答。

单击隐藏图章

我写了好鸡儿久，记得给我设置一下最佳答案

import math
def is_prime(number): #判断是否为素数的函数，如果是，返回True,反之返回True
if number > 1: #如果输入的数小于1， 1和0并不是素数
if number == 2: #2是素数，直接返回True
return True
if number % 2 == 0: #number余2等于0就说明不是素数，返回False
return False
for current in range(3, int(math.sqrt(number) + 1), 2): #将3 到根号number 中的所有数，循环放入current
if number % current == 0: #如果3 到根号number 其中任何一个数可以整除number，那它就不是素数
return False
return True #反之如果 3 至根号number 中的所有数都不能整除number，他就是一个素数
return False
def get_primes(number): #这里传入的number，其实是从3开始传入的
while True: #进入无限循环
if is_prime(number): #判断是否number是否为素数
yield number #如果是素数,就返回number, get_primes() 函数在此暂停！注意是暂停不是释放，下次调用的时候会继续从这里开始。
number += 1 #当下一次调用get_primes() 函数时，会执行 number 自加一，然后继续循环。
def solve():
total = 2 #
for next_prime in get_primes(3): #传入3,for .. in .. 关键字会不断调用get_primes() 函数，注意是一遍又一遍的调用，因为我们在get_primes()函数中并没有设置什么时候跳出死循环，所以它会一直生成新的素数
if next_prime < 2000000: #如果输出的素数 next_prime 是小于2000000的，就是我们需要的数，把它加给total
total += next_prime
else: #如果以及超出了2000000，将跳出死循环，不再获取素数
print(total) #打印出2000000以下的所有素数之和.
return #这里返回空值，其实是将return 当作break来使用，跳出这个for循环，因为get_primes() 是一个无限的生成器，所以需要跳出它.
if __name__ == '__main__': #这个代码的意思是如果是本文件运行就运行下列代码
solve()

复制代码

a3522661110 · 发表于 2018-6-3 22:50:40

simplerjiang 发表于 2018-6-3 21:46
我写了好鸡儿久，记得给我设置一下最佳答案

万分感谢大神，祝你升职加薪！

simplerjiang · 发表于 2018-6-3 23:28:02

a3522661110 发表于 2018-6-3 22:50
万分感谢大神，祝你升职加薪！

客气啦

账号		自动登录	找回密码
密码			立即注册