編程找出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以內的素數並求和，就是這樣簡單而又高效的。我們通過學習這個例子，小小的認識了一下時間複雜度和空間換時間的思想，相信會有不少收穫。