国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

Eratosthenes 之篩算法（尋找質數）

Shimmer / 3064人閱讀

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

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

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

Eratosthenes 之篩算法思路

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

Boolean數組實現 
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實現

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和數組的對比結果

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




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

引發思考的問題

但是！但是！但是！


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


另外一臺電腦跑出來的結果，利用數組實現（也就是上面的ArrayTest）的速度非?？?，經常時間在16-32毫秒之間。而用BitSet實現（也就是上面的BitSetTest）的卻是150-160左右。


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


算法的原理和實現已經懂了一些，但是帶出來了這些問題，有木有大神解釋一下啊。

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

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

相關文章

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

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

    Cruise_Chan 評論0 收藏0

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

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

    biaoxiaoduan 評論0 收藏0

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

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

    Martin91 評論0 收藏0

  • PHP算法之判斷是否是質數

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

    Eidesen 評論0 收藏0

  • RSA加密算法中的數學

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

    ?xiaoxiao, 評論0 收藏0

發表評論

0條評論

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