Python實現100以內判斷素數

素數，又稱質數，是指在大於1的自然數中，除了1和它本身以外，不能被其他自然數整除的數。在計算機編程中，判斷一個數是否為素數一直是一個經典的問題，本文將介紹如何使用Python實現100以內素數的判斷。

一、素數的判斷方法

判斷一個數是否為素數有多種方法，以下介紹其中兩種。

1.試除法

首先我們可以通過試除法來判斷一個數是否為素數。假設要判斷的數為n，首先從2開始，一直到n-1逐個嘗試除以n，如果都除不盡，那麼n就是素數，反之則不是。

def is_prime(n):
    for i in range(2,n):
        if n%i == 0:
            return False
    return True

使用上述代碼即可判斷一個數是否為素數。需要注意的是，這個演算法的時間複雜度為O(n)，並不是最優的演算法。

2. Eratosthenes篩法

Eratosthenes篩法是一種用來求一定範圍內所有素數的演算法。演算法的流程如下：

1.用2~n之間的所有數初始化一個表，將表中所有的數標記為1。

2.從2開始，將表中所有2的倍數標記為0。

3.從3開始，如果這個數還沒有被標記為0，那麼將表中所有它的倍數標記為0。

4.重複第3步，直到處理完n為止。

最終所有值為1的下標即為素數。

def eratosthenes(n):
    primes = [1]*n
    primes[0],primes[1] = 0,0
    for i in range(2,int(n**0.5)+1):
        if primes[i]:
            for j in range(i**2,n,i):
                primes[j] = 0
    return [x for x in range(n) if primes[x]]

使用上述代碼即可返回100以內的所有素數，由於演算法的時間複雜度為O(n log log n)，因此在計算大量素數的情況下，效率更高。

二、完整代碼

def is_prime(n):
    for i in range(2,n):
        if n%i == 0:
            return False
    return True
    
def eratosthenes(n):
    primes = [True]*n
    primes[0],primes[1] = False,False
    for i in range(2,int(n**0.5)+1):
        if primes[i]:
            for j in range(i**2,n,i):
                primes[j] = False
    return [x for x in range(n) if primes[x]]
    
print("試除法：", [x for x in range(2,101) if is_prime(x)])
print("Eratosthenes篩法：", eratosthenes(100))

以上為完整的Python代碼，可以直接複製粘貼到IDE或者Jupyter Notebook中運行。

三、總結

通過本文我們了解了兩種演算法去判斷素數，試除法和Eratosthenes篩法，其中Eratosthenes篩法時間複雜度更低。若需要判斷大量素數時，建議使用Eratosthenes篩法來實現。