本文将会介绍如何使用编程语言找出100以内的所有质数并求和。而质数，指的是只能被1和它本身整除的数字。
一、判断质数的算法
要找出100以内的质数，首先要搞清楚什么是质数，以及如何判断一个数是不是质数。我们可以采用最简单粗暴的方法——暴力枚举所有小于等于该数的正整数，然后判断能否被整除。但这种方法显得低效且烦琐，因此我们需要采用更为高效的方法——埃氏筛法。
埃氏筛法，顾名思义就是埃拉托色尼筛法的简称。埃拉托色尼是一位古希腊人，他提出了一种筛选质数的方法。埃氏筛法是一种用来查找一定范围内素数的算法，该算法以空间换时间，在一定范围内求质数比暴力枚举有效得多。
根据埃氏筛法，我们先把2~n之间的所有数字列出来，然后把2留下；把所有2的倍数删除掉，然后把下一个留下；再把剩下的数中第一个是3的倍数的数留下，再删掉所有3的倍数。依此类推，直到把n内所有的素数都留下来，也就是所谓的素数表。这个过程中不要忘了每次留下一个新的素数并剔除其倍数。
二、代码实现
下面给出Python语言的代码实现，使用埃氏筛法查找100以内的素数并求和：
def prime_numbers(n):
"""
:param n: 限制的范围。例如找100以内的素数，n=100
:return: 返回n以内的全部素数
"""
lst = range(2,n)
p = 2
while True:
lst = filter(lambda x: x % p != 0 or x == p, lst)
# lambda表达式：简单表达式，x如果不是p的倍数或x本身就是p，就保留它
p = lst[0]
if p ** 2 > n:
break
return lst
# 调用函数并求和
result = sum(prime_numbers(100))
print(result)
这个函数首先构建了一个不包括0和1的列表，然后从2开始一步步筛选出素数。其中，利用filter()函数来实现一个筛选器，筛掉能被当前素数整除的数。这里使用的是lambda表达式，这个表达式实际上定义了一个函数对象。最后，如果遍历完素数表中所有的偶数，余下的是奇数，就是n以内的所有素数。最后对素数进行求和。
三、算法分析
代码实现利用了时间复杂度为O(nlogn)的算法。其原理是倍数法，但是在实现时采用了filter函数来进行筛除。由于filter函数也要对每个值都进行比较，所以时间复杂度略高。但相比直接暴力枚举，这种算法还是足够高效的。
借助埃氏筛法找出100以内的素数并求和，就是这样简单而又高效的。我们通过学习这个例子，小小的认识了一下时间复杂度和空间换时间的思想，相信会有不少收获。
原创文章，作者：DBCSD，如若转载，请注明出处：https://www.506064.com/n/375054.html
微信扫一扫 
支付宝扫一扫 