成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

線性素?cái)?shù)篩選（linear sieve for prime number）

biaoxiaoduan / 848人閱讀

摘要：轉(zhuǎn)載到其他平臺(tái)前也請(qǐng)通知我。算法分析由于我們每次尋找的素?cái)?shù)時(shí)，都從開(kāi)始，逐漸上除，最后到為止，確認(rèn)是否是素?cái)?shù)。接著繼續(xù)排除其有關(guān)合數(shù)。在速度上有略微提升，但是它的算法是主動(dòng)忽略的相關(guān)合數(shù)，實(shí)際意義并不是很大。

偶然發(fā)現(xiàn)了這個(gè)和stackoverflow很像的地方。打算寫(xiě)些專欄，一方面，記錄自己學(xué)到的東西。另一方面，也把這些分享給大家。無(wú)論是內(nèi)容錯(cuò)誤還是解釋方式不好，都?xì)g迎各位拍磚。轉(zhuǎn)載到其他平臺(tái)前也請(qǐng)通知我。

本篇的IDE是Pycharm，使用的是Python 3 的基本interpreter
問(wèn)題起源

這個(gè)問(wèn)題起源于我在想尋找最大素?cái)?shù)的時(shí)候誕生的。出現(xiàn)這個(gè)問(wèn)題，一開(kāi)始的想法是通過(guò)暴力破解來(lái)達(dá)成目的，舉例的話，就以尋找第20000個(gè)素?cái)?shù)開(kāi)始吧

算法演繹 
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))

結(jié)果是:

find 224737 in 151.33826684951782 seconds

Process finished with exit code 0

151秒，感覺(jué)花了好長(zhǎng)時(shí)間，顯然這不是一個(gè)有效率的方法。

算法分析

由于我們每次尋找的素?cái)?shù)時(shí)，都從2開(kāi)始，逐漸上除，最后到num/2為止，確認(rèn)是否是素?cái)?shù)。那所用的效率就是
$$ O(N^2) $$

查找了一些文獻(xiàn)以后，看到了一種方法:線性素?cái)?shù)篩選:埃拉托斯特尼篩法（Sieve of Eratosthenes）

在每次我們確定素?cái)?shù)的時(shí)候，將其之后的有關(guān)合數(shù)進(jìn)行排除，每一次在尋找下個(gè)素?cái)?shù)時(shí)，必然能一次性找到，而不用逐漸去加1來(lái)尋找。接著繼續(xù)排除其有關(guān)合數(shù)。那這樣所用效率就變成了
$$O(N*log(log(N)))$$
這里第一個(gè)N來(lái)自于尋找下個(gè)素?cái)?shù)，而log(log(N)來(lái)自于尋找各個(gè)素?cái)?shù)的合數(shù)，而這個(gè)算法，也需要一個(gè)$$O(N)$$的存儲(chǔ)空間，我這里用了5000000的存儲(chǔ)空間。而這是一個(gè)偽的polynomial算法。
wiki中顯示了一種優(yōu)化方法，可以在$$O(N)$$中完成，但相對(duì)的需要$$O(n^{1/2}loglog n/log n)$$的存儲(chǔ)空間。這里給予鏈接，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))

結(jié)果為：

find 224737 in 0.427901029586792 seconds

Process finished with exit code 0

0.4秒，非常迅速。

相關(guān)算法

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

無(wú)關(guān)問(wèn)題 
===============================這里是與主題無(wú)關(guān)的分割線===============================

初用segment fault感覺(jué)還是不太一樣，在以前的寫(xiě)博客習(xí)慣下，隨便試了一些方法，除了tab之外還沒(méi)有找到特別有趣的特殊格式。特別例如平方號(hào)等特殊符號(hào)，沒(méi)能夠?qū)嶒?yàn)出來(lái)。官方是否能出一份文章特殊符號(hào)和格式的使用說(shuō)明呢？

以上問(wèn)題，非常感謝高陽(yáng)sunny的迅速回復(fù)，祝segment fault越辦越出眾！
一欄一槽 
===============================這里是與上述都無(wú)關(guān)的分割線===============================

聽(tīng)說(shuō)一位同學(xué)要去人民大學(xué)讀研，去寒暄了一下：
“你要去人大？”
“恩”
“什么時(shí)候去當(dāng)常委？dog rich, don"t forget!”
“......”
于是我回到美帝以后，發(fā)現(xiàn)又遭到報(bào)應(yīng)性冷空氣了。。。



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

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/37604.html

相關(guān)文章

  • [Leetcode] Count Primes 數(shù)素?cái)?shù)

    摘要：利用這個(gè)性質(zhì)，我們可以建立一個(gè)素?cái)?shù)數(shù)組，從開(kāi)始將素?cái)?shù)的倍數(shù)都標(biāo)注為不是素?cái)?shù)。第一輪將等表為非素?cái)?shù)，然后遍歷到，發(fā)現(xiàn)沒(méi)有被標(biāo)記為非素?cái)?shù)，則將等標(biāo)記為非素?cái)?shù)，一直到為止，再數(shù)一遍素?cái)?shù)數(shù)組中有多少素?cái)?shù)。代碼將的倍倍倍都標(biāo)記為非素?cái)?shù) Count Primes Description: Count the number of prime numbers less than a non-nega...

    Achilles 評(píng)論0 收藏0

  • 204. Count Primes

    摘要：題目鏈接思路首先要知道如何判斷一個(gè)數(shù)字是否為素?cái)?shù)。具體方法可以看這里其次，如果樸素的判斷，那么會(huì)因?yàn)樾实紫露瑫r(shí)。所以在我們每次找到素?cái)?shù)的時(shí)候，可以把素?cái)?shù)的倍數(shù)都標(biāo)記為非素?cái)?shù)。這樣可以節(jié)省輪詢的時(shí)間。算法復(fù)雜度時(shí)間空間代碼 題目鏈接：Counting Primes 思路：首先要知道如何判斷一個(gè)數(shù)字是否為素?cái)?shù)。具體方法可以看這里 其次，如果樸素的判斷，那么會(huì)因?yàn)樾实紫露瑫r(shí)。所以在我...

    王笑朝 評(píng)論0 收藏0

  • JavaScript中的算法（附10道面試常見(jiàn)算法題解決方法和思路）

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

    Cruise_Chan 評(píng)論0 收藏0

  • 歐拉函數(shù)(Euler' totient function )

    摘要：傳送門(mén)這個(gè)就是主角歐拉函數(shù)。在數(shù)論中，對(duì)正整數(shù)，歐拉函數(shù)是小于或等于的正整數(shù)中與互質(zhì)的數(shù)的數(shù)目。歐拉函數(shù)實(shí)際上是模的同余類(lèi)所構(gòu)成的乘法群即環(huán)的所有單位元組成的乘法群的階。 歐拉函數(shù)(Euler totient function ) Author: Jasper Yang School: Bupt 前言 gamma函數(shù)的求導(dǎo)會(huì)出現(xiàn)所謂的歐拉函數(shù)（phi），在一篇論文中我需要對(duì)好幾個(gè)歐...

    lewinlee 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

閱讀需要支付1元查看
<