编程找出100以内的质数并求和

本文将会介绍如何使用编程语言找出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以内的素数并求和，就是这样简单而又高效的。我们通过学习这个例子，小小的认识了一下时间复杂度和空间换时间的思想，相信会有不少收获。