闲聊质数

前几天看一个故事：

1970年，赞比亚的玛丽·尤肯达修女给当时NASA太空航行中心的科学副总监恩斯特·史都林格博士写信问道：“目前地球上还有这么多小孩子吃不上饭，你怎么还能舍得为远在火星的项目花费数十亿美元？”

史都林格很快给玛丽·尤肯达修女回了信。大意是，很多看起来暂时无用的基础科学研究，其实才是推动生产力和人类进步的最大力量。他这封真挚的回信随后由NASA以《为什么要探索宇宙》为题发表。

高中上学的时候，学了很多当时觉得很无聊的东西，比如矩阵。感觉数学家们吃饱了撑得搞这些数字游戏。后来自己接触了游戏行业，才知道原来这些枯燥无味的数字真的能够解决很多实际问题。比如计算机图形学，根本就离不开矩阵运算。

质数，可能很多人只是知道它的一个定义。但是我们为什么要在一堆自然数中寻找质数呢，这其实最早源于古希腊数学家们的直觉。从乘法的角度看，这些质数是最小的单位了，不能再被分解成两个因数。而这样特殊的一个数字群体，总有他特殊的意义。

就像我们的宇宙，存在着一些常数，普朗克常数，法拉第常数等等。那么是否有另外一个宇宙，存在着与我们不同各种常数呢？我们找到了这些特殊的数字，对理解我们所生活的世界是有很大帮助的。

质数近来被利用在密码学上，所谓的公钥就是将想要传递的信息在编码时加入质数，编码之后传送给收信人，任何人收到此信息后，若没有此收信人所拥有的密钥，则解密的过程中（实为寻找素数的过程），将会因为找质数的过程（分解质因数）过久，使即使取得信息也会无意义。

在汽车变速箱齿轮的设计上，相邻的两个大小齿轮齿数最好设计成质数，以增加两齿轮内两个相同的齿相遇啮合次数的最小公倍数，可增强耐用度减少故障。

在害虫的生物生长周期与杀虫剂使用之间的关系上，杀虫剂的质数次数的使用也得到了证明。实验表明，质数次数地使用杀虫剂是最合理的：都是使用在害虫繁殖的高潮期，而且害虫很难产生抗药性。

以质数形式无规律变化的导弹和鱼雷可以使敌人不易拦截。

那么如何取得质数呢？有很多种方法，最适合计算机的应该是埃拉托色尼筛法：

首先，列出从2开始的数。然后，将2记在素数列表上，再划去所有2的倍数。根据定义，剩下的最小的数——在这里是3——必定是素数。将这个数记在素数列表上，再划去所有它的倍数，这样又会剩下一些数，取其中最小的，如此反复操作。最后剩下的都是素数。

作为一个码农，我当然得把算法转换为代码：

<!DOCTYPE HTML>
<html>
<head>
    <meta http-equiv="Content-Type" content="text/html;charset=utf-8">
    <meta content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=0" name="viewport" />
    <title>prime</title>
    <style>
        #wrap{
            width:320px;
            margin:0 auto;
            text-align: center;
        }
        #output{
            text-align:left;
        }
        var{
            color:red;
        }
    </style>
</head>
<body>

<div id="wrap">
    <h1>算质数</h1>
    <br>
    <div>
        <input id="max" type="text" />以内的质数
        <input type="button" id="button" value="计算" />
    </div>
    <br>
    <div id="output"></div>
</div>

<script>
var button_dom=document.getElementById("button");
var max_dom=document.getElementById("max");
var output_dom=document.getElementById("output");
button_dom.onclick=function(){
    var value=max_dom.value;
    output_dom.innerHTML="<var>计算中...</var>";
    if(value){
        //获取质数数组
        var startTime=(new Date()).getTime();
        var arr=getPrime(parseInt(value));
        var nowTime=(new Date()).getTime();
        var time=(nowTime-startTime)/1000;
        //
        var str=arrToString(arr);
        str="<strong>"+value+"</strong> 以内的质数有<strong> "+arr.length+" </strong>个：<var>（计算耗时"+time+"秒）</var><br>"+str;
        //
        output_dom.innerHTML=str;
    
    }else{
        output_dom.innerHTML="<var>请输入素数的范围</var>";
    }
}
function arrToString(arr){//数组转化为字符串
    return arr.join(" ");
}
function getPrime(max){//获取max以内的质数
    var num=[];
    var prime=[];
    for(var i=2;i<=max;i++){
        num[i-2]=i;
    }
    for(var i=0;i<num.length;i++){
        if(num[i]===0){continue;}
        var key=num[i];
        prime.push(key);
        deleByKey(num,key);    
    }
    return prime;
}
function deleByKey(arr,key){//删除数组内能够被key整除的数
    var len=arr.length;
    for(var i=len-1;i>=0;i--){
        if(arr[i]%key===0){
            arr[i]=0;
        }
    }
}
</script>
</body>
</html>

测试地址：

http://sjusttest.sinaapp.com/prime.html

最后顺带为ie9默哀：