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

資訊專欄INFORMATION COLUMN

Eratosthenes 之篩算法（尋找質(zhì)數(shù)）

Shimmer / 3070人閱讀

摘要：有一個例子是之篩算法，這個算法的主要作用是查找一定范圍之內(nèi)的所有質(zhì)數(shù)，對此比較感興趣，所以用數(shù)組和各做了一遍，又在兩臺電腦上各實(shí)現(xiàn)了兩種算法。

閱讀《Java核心技術(shù)》的時(shí)候，讀到了BitSet這個集合。
有一個例子是Eratosthenes 之篩算法，這個算法的主要作用是查找一定范圍之內(nèi)的所有質(zhì)數(shù)，對此比較感興趣，所以用Boolean數(shù)組和BitSet各做了一遍，又在兩臺電腦上各實(shí)現(xiàn)了兩種算法。

在實(shí)現(xiàn)的過程中，遇到了一些問題，會在最后提出，這里不說廢話了，先說正事~

Eratosthenes 之篩算法思路

由于一個合數(shù)總是可以分解成若干個質(zhì)數(shù)的乘積，那么如果把質(zhì)數(shù)（最初只知道2是質(zhì)數(shù)）的倍數(shù)都去掉，那么剩下的就是質(zhì)數(shù)了。
例如要查找100以內(nèi)的質(zhì)數(shù)，首先2是質(zhì)數(shù)，把2的倍數(shù)去掉；此時(shí)3沒有被去掉，可認(rèn)為是質(zhì)數(shù)，所以把3的倍數(shù)去掉；再到5，再到7，7之后呢，因?yàn)?，9，10剛才都被去掉了，而100以內(nèi)的任意合數(shù)肯定都有一個因子小于10（100的開方），所以，去掉，2，3，5，7的倍數(shù)后剩下的都是質(zhì)數(shù)了。

Boolean數(shù)組實(shí)現(xiàn) 
public class ArrayTest
{
    public static void main(String[] args) 
    {

        int sum = 0;
        final int TOTAL = 2_000_001;

        Boolean[] array = new Boolean[TOTAL];

        long startTime = System.currentTimeMillis();

        for(int i = 2;i
BitSet實(shí)現(xiàn)

import java.util.BitSet;

public class BitSetTest
{
    public static void main(String[] args) 
    {

        int sum = 0;
        final int TOTAL = 2_000_001;

        BitSet aBitSet = new BitSet(TOTAL);

        long startTime = System.currentTimeMillis();

        for(int i = 2;i
BitSet和數(shù)組的對比結(jié)果

然后各測試了三次，測試的結(jié)果是這樣子的：




可以看到三次平均下來，BitSet的性能還是稍微好一些的。

引發(fā)思考的問題

但是！但是！但是！


我在另外一臺電腦上用相同的代碼跑出來的結(jié)果卻很不一樣。


另外一臺電腦跑出來的結(jié)果，利用數(shù)組實(shí)現(xiàn)（也就是上面的ArrayTest）的速度非常快，經(jīng)常時(shí)間在16-32毫秒之間。而用BitSet實(shí)現(xiàn)（也就是上面的BitSetTest）的卻是150-160左右。


兩臺機(jī)器的配置是一樣的，win7，32位，4GB，3.2GHZ。
一開始以為是編譯器的問題，后來發(fā)現(xiàn)不用編譯器用命令行得到的結(jié)果也是有差異的。


算法的原理和實(shí)現(xiàn)已經(jīng)懂了一些，但是帶出來了這些問題，有木有大神解釋一下啊。

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

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

相關(guān)文章

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

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

    Cruise_Chan 評論0 收藏0

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

    摘要：轉(zhuǎn)載到其他平臺前也請通知我。算法分析由于我們每次尋找的素?cái)?shù)時(shí)，都從開始，逐漸上除，最后到為止，確認(rèn)是否是素?cái)?shù)。接著繼續(xù)排除其有關(guān)合數(shù)。在速度上有略微提升，但是它的算法是主動忽略的相關(guān)合數(shù)，實(shí)際意義并不是很大。 偶然發(fā)現(xiàn)了這個和stackoverflow很像的地方。打算寫些專欄，一方面，記錄自己學(xué)到的東西。另一方面，也把這些分享給大家。無論是內(nèi)容錯誤還是解釋方式不好，都?xì)g迎各位拍磚。轉(zhuǎn)載...

    biaoxiaoduan 評論0 收藏0

  • 算法之不定期更新（一）（2018-04-12）

    摘要：算法的確有他獨(dú)特的魅力。然后我在做這個題的時(shí)候，其實(shí)也用到了類似質(zhì)因數(shù)分解，只是其實(shí)我們可以更好的利用到因數(shù)這一個特性。判斷一個數(shù)是否是質(zhì)數(shù)質(zhì)數(shù)列表一開始我們認(rèn)為每一個數(shù)都可能是自身的冪線性篩為質(zhì)數(shù)遍歷質(zhì)數(shù)列表為質(zhì)數(shù)的冪 前言 從三月份到現(xiàn)在，大大小小筆試了十幾家公司（主要是因?yàn)橐恢眘olo code，沒人內(nèi)推），然后也能感覺到自己的進(jìn)步把。從編程題只能ac一題到后來的ak。今天面騰訊...

    Martin91 評論0 收藏0

  • PHP算法之判斷是否是質(zhì)數(shù)

    摘要：質(zhì)數(shù)的定義質(zhì)數(shù)又稱素?cái)?shù)。一個大于的自然數(shù)，除了和它自身外，不能整除其他自然數(shù)的數(shù)叫做質(zhì)數(shù)否則稱為合數(shù)。實(shí)現(xiàn)思路循環(huán)所有可能的備選數(shù)字，然后和中間數(shù)以下且大于等于的整數(shù)進(jìn)行整除比較，如果能夠被整數(shù)，則肯定不是質(zhì)數(shù)，相反，就是質(zhì)數(shù)。 showImg(https://farm5.staticflickr.com/4256/35315926115_fcde5c8234_c.jpg); 質(zhì)數(shù)的定...

    Eidesen 評論0 收藏0

  • RSA加密算法中的數(shù)學(xué)

    摘要：背景不對稱加密算法可是算是世界上最重要的加密算法，其中包括我們熟悉的的加密?，F(xiàn)在我們分步來看，這個全球最重要的加密算法，都需要哪些數(shù)學(xué)知識。我們常說的算法中的多少位，就是用二進(jìn)制表示后的位數(shù)，在我們例子就是位。其中表示兩個數(shù)的最大公約數(shù)。 背景 RSA不對稱加密算法可是算是世界上最重要的加密算法，其中包括我們熟悉的https的加密。為了完全弄明白他的實(shí)現(xiàn)原理，我們需要對數(shù)論這門學(xué)科，有...

    ?xiaoxiao, 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<