Eratosthenes 之筛算法（寻找质数）

Shimmer 发布于2019-08-14 12:27 / 3001人阅读

摘要：有一个例子是之筛算法，这个算法的主要作用是查找一定范围之内的所有质数，对此比较感兴趣，所以用数组和各做了一遍，又在两台电脑上各实现了两种算法。

阅读《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。
一开始以为是编译器的问题，后来发现不用编译器用命令行得到的结果也是有差异的。
算法的原理和实现已经懂了一些，但是带出来了这些问题，有木有大神解释一下啊。

GPU云服务器云服务器质数c语言算法最简单的质数算法最短寻找时间优先和电梯调度算法 Eratosthenes

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64490.html

JavaScript中的算法（附10道面试常见算法题解决方法和思路）

摘要：中的算法附道面试常见算法题解决方法和思路关注每日一道面试题详解面试过程通常从最初的电话面试开始，然后是现场面试，检查编程技能和文化契合度。值得记住的数组方法有和。一个好的解决方案是使用内置的方法。 JavaScript中的算法（附10道面试常见算法题解决方法和思路）关注github每日一道面试题详解 Introduction 面试过程通常从最初的电话面试开始，然后是现场面试，检查编程...

Cruise_Chan 2019-08-26 10:22 评论0 收藏0
线性素数筛选（linear sieve for prime number）

摘要：转载到其他平台前也请通知我。算法分析由于我们每次寻找的素数时，都从开始，逐渐上除，最后到为止，确认是否是素数。接着继续排除其有关合数。在速度上有略微提升，但是它的算法是主动忽略的相关合数，实际意义并不是很大。偶然发现了这个和stackoverflow很像的地方。打算写些专栏，一方面，记录自己学到的东西。另一方面，也把这些分享给大家。无论是内容错误还是解释方式不好，都欢迎各位拍砖。转载...

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

摘要：算法的确有他独特的魅力。然后我在做这个题的时候，其实也用到了类似质因数分解，只是其实我们可以更好的利用到因数这一个特性。判断一个数是否是质数质数列表一开始我们认为每一个数都可能是自身的幂线性筛为质数遍历质数列表为质数的幂前言从三月份到现在，大大小小笔试了十几家公司（主要是因为一直solo code，没人内推），然后也能感觉到自己的进步把。从编程题只能ac一题到后来的ak。今天面腾讯...

Martin91 2019-08-22 16:16 评论0 收藏0
PHP算法之判断是否是质数

摘要：质数的定义质数又称素数。一个大于的自然数，除了和它自身外，不能整除其他自然数的数叫做质数否则称为合数。实现思路循环所有可能的备选数字，然后和中间数以下且大于等于的整数进行整除比较，如果能够被整数，则肯定不是质数，相反，就是质数。 showImg(https://farm5.staticflickr.com/4256/35315926115_fcde5c8234_c.jpg); 质数的定...

Eidesen 2019-07-01 12:31 评论0 收藏0
RSA加密算法中的数学

摘要：背景不对称加密算法可是算是世界上最重要的加密算法，其中包括我们熟悉的的加密。现在我们分步来看，这个全球最重要的加密算法，都需要哪些数学知识。我们常说的算法中的多少位，就是用二进制表示后的位数，在我们例子就是位。其中表示两个数的最大公约数。背景 RSA不对称加密算法可是算是世界上最重要的加密算法，其中包括我们熟悉的https的加密。为了完全弄明白他的实现原理，我们需要对数论这门学科，有...

?xiaoxiao, 2019-08-21 17:53 评论0 收藏0