Python 數域篩是一種基于區間篩法的素數篩選算法。我們在這里將詳細的介紹實現步驟,完整代碼如下:
def prime(n): """返回小于等于n的素數列表""" primes = [] is_prime = [True] * (n + 1) is_prime[0] = is_prime[1] = False for i in range(2, n + 1): if is_prime[i]: primes.append(i) for j in primes: if i * j >n: break is_prime[i * j] = False if i % j == 0: break return primes
代碼解讀:
1. 首先定義返回小于等于n的素數列表的函數prime。
2. 創建一個長度為n+1,以True填充的列表is_prime表示每個數是否為素數。0和1不是素數,因此標記為False。
3. 從2開始循環到n,若i是素數,則加入primes列表中。
4. 對i加入primes列表中的每個素數j(小于等于根號i)做如下處理:
a. 若i*j大于n則跳出循環。
b. 標記i*j為非素數。
c. 若j能整除i,則跳出循環。
5. 返回primes列表即為小于等于n的素數列表。
使用數域篩法進行素數篩選,時間復雜度為O(nloglogn),比傳統篩法更具優越性能,尤其在極大的數字下表現更出色。同時python語言的簡潔,讓我們更好的閱讀和理解算法步驟。
下一篇c json排序