列出小於某數的全部質數
編輯：關於JavaScript
前幾天看一個故事：
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>
下面是改進後的代碼,計算質數的效率有所提高：
<!DOCTYPE HTML>
<html>
<head>
<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>
button.onclick = function() {
var value = max.value;
output.innerHTML = "<var>計算中...</var>";
if (value) {
//獲取質數數組
var startTime = (new Date()).getTime();
var arr = getPrime2(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.innerHTML = str;
} else {
output.innerHTML = "<var>請輸入素數的范圍</var>";
}
}
function arrToString(arr) { //數組轉化為字符串
return arr.join(" ");
}
function getPrime2(max) { //獲取max以內的質數
var prime = [];
for (var i = 2; i <= max; i++) {
if (isPrimeNum(i, prime)) {
prime.push(i);
}
}
return prime;
}
function isPrimeNum(n, arr) {
if (n < 2) {
return false;
}
if (n == 2) {
return true;
}
if (!arr || !arr.length) {
return false;
}
for (var p = 0; p < arr.length; p++) {
if (n % arr[p] == 0) {
return false;
}
}
return true;
}
</script>
</body>
</html>
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>
下面是改進後的代碼,計算質數的效率有所提高：
<!DOCTYPE HTML>
<html>
<head>
<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>
button.onclick = function() {
var value = max.value;
output.innerHTML = "<var>計算中...</var>";
if (value) {
//獲取質數數組
var startTime = (new Date()).getTime();
var arr = getPrime2(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.innerHTML = str;
} else {
output.innerHTML = "<var>請輸入素數的范圍</var>";
}
}
function arrToString(arr) { //數組轉化為字符串
return arr.join(" ");
}
function getPrime2(max) { //獲取max以內的質數
var prime = [];
for (var i = 2; i <= max; i++) {
if (isPrimeNum(i, prime)) {
prime.push(i);
}
}
return prime;
}
function isPrimeNum(n, arr) {
if (n < 2) {
return false;
}
if (n == 2) {
return true;
}
if (!arr || !arr.length) {
return false;
}
for (var p = 0; p < arr.length; p++) {
if (n % arr[p] == 0) {
return false;
}
}
return true;
}
</script>
</body>
</html>
- 上一頁:javascript正則表達式基礎篇
- 下一頁:js獲取某月最後一天的日期
小編推薦
熱門推薦