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

Shimmer 發(fā)布于2019-08-14 12:27 / 3154人閱讀

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

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

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

Eratosthenes 之篩算法思路

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

Boolean數(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實現(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ù)組的對比結果
然后各測試了三次，測試的結果是這樣子的：

可以看到三次平均下來，BitSet的性能還是稍微好一些的。
引發(fā)思考的問題
但是！但是！但是！
我在另外一臺電腦上用相同的代碼跑出來的結果卻很不一樣。
另外一臺電腦跑出來的結果，利用數(shù)組實現(xiàn)（也就是上面的ArrayTest）的速度非?？欤?jīng)常時間在16-32毫秒之間。而用BitSet實現(xiàn)（也就是上面的BitSetTest）的卻是150-160左右。
兩臺機器的配置是一樣的，win7，32位，4GB，3.2GHZ。
一開始以為是編譯器的問題，后來發(fā)現(xiàn)不用編譯器用命令行得到的結果也是有差異的。
算法的原理和實現(xiàn)已經(jīng)懂了一些，但是帶出來了這些問題，有木有大神解釋一下啊。

云服務器 GPU云服務器質數(shù)c語言算法最簡單的質數(shù)算法最短尋找時間優(yōu)先和電梯調度算法 Eratosthenes

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

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

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

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

Cruise_Chan 2019-08-26 10:22 評論0 收藏0
線性素數(shù)篩選（linear sieve for prime number）

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

biaoxiaoduan 2019-07-24 18:07 評論0 收藏0
算法之不定期更新（一）（2018-04-12）

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

Martin91 2019-08-22 16:16 評論0 收藏0
PHP算法之判斷是否是質數(shù)

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

Eidesen 2019-07-01 12:31 評論0 收藏0
RSA加密算法中的數(shù)學

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

?xiaoxiao, 2019-08-21 17:53 評論0 收藏0