線性素數篩選（linear sieve for prime number）

biaoxiaoduan 發布于2019-07-24 18:07 / 836人閱讀

摘要：轉載到其他平臺前也請通知我。算法分析由于我們每次尋找的素數時，都從開始，逐漸上除，最后到為止，確認是否是素數。接著繼續排除其有關合數。在速度上有略微提升，但是它的算法是主動忽略的相關合數，實際意義并不是很大。

偶然發現了這個和stackoverflow很像的地方。打算寫些專欄，一方面，記錄自己學到的東西。另一方面，也把這些分享給大家。無論是內容錯誤還是解釋方式不好，都歡迎各位拍磚。轉載到其他平臺前也請通知我。

本篇的IDE是Pycharm，使用的是Python 3 的基本interpreter

問題起源

這個問題起源于我在想尋找最大素數的時候誕生的。出現這個問題，一開始的想法是通過暴力破解來達成目的，舉例的話，就以尋找第20000個素數開始吧

算法演繹

import time

def func(num):
    # since once i larger than num//2, num will not be divisible by any i increment
    for i in range(2, num//2+1):
        if num % i == 0:
            return 0
    return 1

def find_prime():
    num = 1
    count = 0
    # find the 20000th prime in the world!
    primeCount = 20000
    while count < primeCount :
        num += 1
        count = func(num)+count
    return num

# count time
start = time.time()
num = find_prime()
end = time.time() -start
print("find %s in %s seconds" % (num,end))

結果是:

find 224737 in 151.33826684951782 seconds

Process finished with exit code 0

151秒，感覺花了好長時間，顯然這不是一個有效率的方法。

算法分析

由于我們每次尋找的素數時，都從2開始，逐漸上除，最后到num/2為止，確認是否是素數。那所用的效率就是
$$ O(N^2) $$

查找了一些文獻以后，看到了一種方法:線性素數篩選:埃拉托斯特尼篩法（Sieve of Eratosthenes）

在每次我們確定素數的時候，將其之后的有關合數進行排除，每一次在尋找下個素數時，必然能一次性找到，而不用逐漸去加1來尋找。接著繼續排除其有關合數。那這樣所用效率就變成了
$$O(N*log(log(N)))$$
這里第一個N來自于尋找下個素數，而log(log(N)來自于尋找各個素數的合數，而這個算法，也需要一個$$O(N)$$的存儲空間，我這里用了5000000的存儲空間。而這是一個偽的polynomial算法。
wiki中顯示了一種優化方法，可以在$$O(N)$$中完成，但相對的需要$$O(n^{1/2}loglog n/log n)$$的存儲空間。這里給予鏈接，Paul Pritchard

算法演繹

def fast_find_prime(n,limit =5000000):
    if limit %2 != 0 :
        limit+=1
    # Assume all numbers are prime number
    primes = [True] *limit
    # Eliminate 0 and 1
    primes[0], primes[1] = [None] *2
    # set count
    count = 0
    # enumerate numbers
    for ind, val in enumerate(primes):
        if val is True:
            # set number false when it is not prime
            # ind will skip not prime numbers
            primes[ind*2::ind] = [False] * (((limit-1)//ind)-1)
            count += 1
        if count == n: return  ind
    return False

#count time
start = time.time()
num = fast_find_prime(20000)
end = time.time() -start
print("find %s in %s seconds" % (num,end))

結果為：

find 224737 in 0.427901029586792 seconds

Process finished with exit code 0

0.4秒，非常迅速。

相關算法

在論壇中提到過一種 Sieve of Atkin 的算法。在速度上有略微提升，但是它的算法是主動忽略2、3、5的相關合數，實際意義并不是很大。有興趣的同學也可以看一下。

無關問題

===============================這里是與主題無關的分割線===============================

初用segment fault感覺還是不太一樣，在以前的寫博客習慣下，隨便試了一些方法，除了tab之外還沒有找到特別有趣的特殊格式。特別例如平方號等特殊符號，沒能夠實驗出來。官方是否能出一份文章特殊符號和格式的使用說明呢？

以上問題，非常感謝高陽sunny的迅速回復，祝segment fault越辦越出眾！

一欄一槽

===============================這里是與上述都無關的分割線===============================

聽說一位同學要去人民大學讀研，去寒暄了一下：
“你要去人大？”
“恩”
“什么時候去當常委？dog rich, don"t forget!”
“......”
于是我回到美帝以后，發現又遭到報應性冷空氣了。。。

14年時初，拜訪康村，和cornell的同學冒著雪天，黃昏時分在康村取景拍下的照片

GPU云服務器云服務器 for 循環數據篩選 js sieve Linear Primes

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/37604.html

[Leetcode] Count Primes 數素數

摘要：利用這個性質，我們可以建立一個素數數組，從開始將素數的倍數都標注為不是素數。第一輪將等表為非素數，然后遍歷到，發現沒有被標記為非素數，則將等標記為非素數，一直到為止，再數一遍素數數組中有多少素數。代碼將的倍倍倍都標記為非素數 Count Primes Description: Count the number of prime numbers less than a non-nega...

Achilles 2019-08-14 12:28 評論0 收藏0
204. Count Primes

摘要：題目鏈接思路首先要知道如何判斷一個數字是否為素數。具體方法可以看這里其次，如果樸素的判斷，那么會因為效率底下而超時。所以在我們每次找到素數的時候，可以把素數的倍數都標記為非素數。這樣可以節省輪詢的時間。算法復雜度時間空間代碼題目鏈接：Counting Primes 思路：首先要知道如何判斷一個數字是否為素數。具體方法可以看這里其次，如果樸素的判斷，那么會因為效率底下而超時。所以在我...

王笑朝 2019-07-30 16:58 評論0 收藏0
JavaScript中的算法（附10道面試常見算法題解決方法和思路）

摘要：中的算法附道面試常見算法題解決方法和思路關注每日一道面試題詳解面試過程通常從最初的電話面試開始，然后是現場面試，檢查編程技能和文化契合度。值得記住的數組方法有和。一個好的解決方案是使用內置的方法。 JavaScript中的算法（附10道面試常見算法題解決方法和思路）關注github每日一道面試題詳解 Introduction 面試過程通常從最初的電話面試開始，然后是現場面試，檢查編程...

Cruise_Chan 2019-08-26 10:22 評論0 收藏0
歐拉函數(Euler' totient function )

摘要：傳送門這個就是主角歐拉函數。在數論中，對正整數，歐拉函數是小于或等于的正整數中與互質的數的數目。歐拉函數實際上是模的同余類所構成的乘法群即環的所有單位元組成的乘法群的階。歐拉函數(Euler totient function ) Author: Jasper Yang School: Bupt 前言 gamma函數的求導會出現所謂的歐拉函數（phi），在一篇論文中我需要對好幾個歐...

lewinlee 2019-07-31 12:23 評論0 收藏0