计算100以内的所有素数（质数）算法思考

2013-12-28

@(blog)

我们做页面的前端们可能很少遇到算法问题，之前也一直没碰到过，在最近的商品sku选择和表格列排序中都遇到了，觉得有必要整体了解下算法的相关知识。前端开发跟算法打交道毕竟不是很多，如果要深入学习，怕是学习曲线太陡了，收益也不大，上网搜了搜，园里的一位朋友推荐《算法解读》，图文并茂，简单易懂，里面有提到计算素数的问题，结合自己的思考，把计算过程整理如下。

概念

在我上小学时，教科书上叫它质数，后来好像改名叫素数了，所以，本文提到的质数和素数是一个概念。什么是素数呢，维基百科里的解释是：素数，指在大于1的自然数中，除了1和此整数自身外，无法被其他自然数整除的数（也可定义为只有1和本身两个因数的数）。

阿king吐槽

这里，鄙人要吐槽下，上小学那会为了学好神马质数，合数，最大公约数的，最小公倍数，不知道消耗了骚年多少脑细胞；现在为了应对实战中的不可能事件却经常在算法书籍中出现的求质数问题，又要燃烧耗尽我多少脑细胞。好吧，也许俺是粗人，不搞数学，不搞科技，孤陋寡闻了，那就看看维基里描述的关于素数的应用吧：

素数近来被利用在密码学上，所谓的公钥就是…（此处略去50字）在汽车变速箱齿轮的设计上…(此处略去30字) 在害虫的生物生长周期与杀虫剂使用之间的关系上…(此处略去40字)。以素数形式无规律变化的导弹和鱼雷可以使敌人不易拦截。

密码学？多高端啊；齿轮设计、害虫生命周期？多大气啊；鱼雷、导弹？多上档次啊。都是白骨精里的高富帅，高富帅里的高精尖的菜，咱们矮穷挫也只能不明觉历了。

吐完了，为了饭碗，咱还得接着啃啊，继续

关于素数的一些注意点

2和3是所有素数中唯一两个连着的数。
2是唯一一个为偶数（双数）的质数。
质数的个数是无穷的
100以内的质数有2，3，5，7，11，13，17，19，23，29，31，37，41，43，47，53，59，61，67，71，73，79，83，89，97，在100内共有25个质数。

算法思考

网上提到的算法有很多，各种语言的实现也有差异。这里讲两种基于js的实现方法，一种是常规的思维，比较好理解，还有一种是跟据定律推算的，效率更高

常规思路

所谓素数就是除1和自身外，无法被其他数整除的数，那就循环比这个数的平方根还小的数，并取模，都不能整除，就是素数了，思路有了，coding吧：

//法一
function prime (num){
    var arr = [],
        start = new Date().getTime(),
        end;
    outer: for (var i=2;i<num;i++){
        for(var j=2;j*j<=i;j++){
            if (i%j==0){
                continue outer;
            }
        }
        arr.push(i);
    }
    end = new Date().getTime();
    console.log(end-start);
    return arr;
}

在chrome下测试，num=1000000时，时间为695ms

筛选过滤

上面的算法经过了两次循环，而且每一次循环的数据都是连续无间断的，下面使用6N±1定律，先筛选出一些数据，再进行循环，理论上这种效率会高很多。

6N±1定侓：任何一个自然数，总是可以表示成如下的形式之一：6N,6N+1,6N+2,6N+3,6N+4,6N+5 (N=0,1,2,3…) 显然，当N>=1时，6N,6N+2,6N+3,6N+4都不是素数，只有形如6N+1和6N+5的自然数有可能是素数（注意：这只是过滤出有可能的数，但未必一定是，比如25=6*4+1，就不是素数）。6N+5又可以表示成6N-1，所以，除了2和3外，所有的素数都可以表示成6n±1的形式。

注意：6N±1只是过滤筛选器，本身不能直接选出素数

//法二
function prime2 (num, filter){
    var start = new Date().getTime(),
        end,
        arr = filter(num),
        newArr = [];

    outer: for (var i=0, len = arr.length ; i<len; i++){
        var temp = arr[i];
        for (var j=2;j*j<=temp;j++){
            if (temp%j==0){
                continue outer;
            }
        }
        newArr.push(temp);
    }
    end = new Date().getTime();
    console.log(end-start);
    return newArr;
}

//6N±1先筛选出有可能的数据
function filterArr (num){
    var arr = [];
    arr.push(2,3);
    for (var i=1; 6*i+1<=num; i++){
        arr.push(6*i-1,6*i+1);
    }
    return arr;
}

prime2(1000000, filterArr);

在chrome下测试，num=1000000时，时间为783ms 。

这就奇怪了，居然和我的理论推论不同，不但没有更快，反而更慢了些，这是怎么回事呢，思来想去，突然眼前一亮，我使用了数组来保存通过6N±1定律筛选出来的数据，这样在第二次的判断时就得从数组读取数据，这肯定比直接读取直接量慢，正好佐证了《高性能JavaScript编程》一书中提到的关于数据访问性能的研究，如下图：

Alt text

对于绝大多数浏览器，各类数据访问的耗时高低是：

直接量 < 局部变量 < 数组 < 对象

看来这种方法还得再优化

筛选法优化

上面的筛选法，之所以引入数组，是因为每筛选一次，会得到二个值6N+1和6N-1，这样就不知道怎么进行下一步的操作了，是分别处理呢，还是…。所以，为了使这里的逻辑更清淅，我先用数组存数据，最后再对这个数组循环一遍。既然数组的读取慢，那就想想如何把存数组这一步去掉，要去掉这一步，得把6N+1和6N-1这两种情况合并成一个逻辑，看下面的推论：

6N-1; 6N+1; 6N+1 == 6N+2-1 == (6N+2)-1 == 2(3N+1)-1

上面的算法是不是似曾相识，在上初中时，经常有类似的证明题，求等式两边相等，老师在黑板上，左减右减，上移下移，左导右导，神奇般地相等了，咯，当时那叫一个不明觉厉啊。

好的，现在6N+1和6N-1的逻缉并做了2(3N+M)-1,这样只要整二次循环，把N的循环做为外层，M做为内层循环，M分别取0和1；就实现了一个表达式生成二类值，看代码:

//法三：
function prime3 (num){
    var arr = [],
        start  = new Date().getTime(),
        end;
    arr.push(2,3);
    outer: for (var i=1; ; i++){
        inner: for (var j = 0; j<=1; j++){
            var temp = 2*(3*i+j)-1;
            if (temp>num){
                break outer;
            }
            for (var l=2; l*l<=temp; l++){
                if (temp%l == 0){
                    continue inner;
                }
            }
            arr.push(temp);
        }
    }
    end = new Date().getTime();
    console.log(end-start);
    return arr;
}

在chrome下测试，num=1000000时，时间为715ms 。晕，理论是完美的，现实又一次伤害了我，花了这么多时间想的算法，实际却和预想的大相径庭，虽然比法二的读数组方式快，但还是没有法一常规思路的快。

我又刷新了5次，以下分别为法一，法二，法三方法运行5次的值和平均值(mac下的chrome):

928,1061,887 981,1036,950 888,996,915 936,971,1001 943,966,871 平均值: 935,1006,925

还好，从平均值来看，我的理论推论是正确的。

但另一方面想想，在有的项目上一味追求代码的算法和性能，带来的实际收益微乎其微，上面的测试是把数据放大到1000000，这时三种方法的区别也只有10几毫秒，与其绞尽脑汁去想复杂耗时的算法，不如想办法把代码写得更简单易懂，这样即使自己过很长时间再读代码，也是很好理解的，所以三种算法选一中的话，我会选法一，常规思路，好记易懂。

这里又一次佐证了《高性能JavaScript编程》书中的一句话：

...但对于大多数日常操作而言,其差异并不大,所以你应当根据代码可读性,可维护性,团队习惯,代码风格来综合决定采用哪种方法。

点击查看评论

悟道前端