前幾天讀到一個故事:1970 年,贊比亞的瑪麗·尤肯達修女給 NASA 太空航行中心的科學副總監恩斯特·史都林格博士寫信問道:「目前地球上還有這麼多小孩子吃不上飯,你怎麼還能捨得為遠在火星的項目花費數十億美元?」史都林格很快回信,大意是:許多看似暫時無用的基礎科學研究,其實才是推動生產力與人類進步的最大力量。這封真摯的回信後來由 NASA 以《為什麼要探索宇宙》為題發表。
上高中時學過很多當時覺得很無聊的東西,比如矩陣,總覺得數學家是在搞數字遊戲。後來接觸游戲行業才明白,這些枯燥的數字真的能解決實際問題——計算機圖形學根本離不開矩陣運算。
質數也是這樣。很多人只知道它的定義,卻未必想過為什麼要在自然數中尋找質數。這最早源於古希臘數學家的直覺:從乘法角度看,質數是最小的單位,無法再分解成兩個因數。這樣特殊的一群數字,自然有其特殊意義。
質數近來被廣泛應用於密碼學。所謂公鑰,就是在編碼時加入質數,收信人若沒有相應密鑰,解密(本質上是分解質因數)會因計算量過大而變得不現實,從而使信息即使被截獲也難以被破解。此外,變速箱相鄰齒輪的齒數設計成質數可增加耐用度、減少故障;以質數次數使用殺蟲劑也被證明更合理;以質數規律無規律變化的導彈和魚雷則更不易被攔截。
那麼如何求質數?最適合計算機的莫過於埃拉托色尼篩法:先列出從 2 開始的數,把 2 記為素數並劃去它所有的倍數;剩下最小的數(此處是 3)必為素數,記下並劃去它的倍數;如此反復,最終剩下的都是素數。
作為一名開發者,我把這個算法寫成了代碼:
<!DOCTYPE HTML>
<html>
<head>
<meta http-equiv="Content-Type" content="text/html;charset=utf-8">
<title>prime</title>
</head>
<body>
<div id="wrap">
<h1>算質數</h1>
<div>
<input id="max" type="text" />以內的質數
<input type="button" id="button" value="計算" />
</div>
<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>個:(計算耗時" + time + "秒)<br>" + str;
output_dom.innerHTML = str;
} else {
output_dom.innerHTML = "<var>請輸入素數的范圍</var>";
}
}
function arrToString(arr) { return arr.join(" "); }
function getPrime(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) {
for (var i = arr.length - 1; i >= 0; i--) {
if (arr[i] % key === 0) { arr[i] = 0; }
}
}
</script>
</body>
</html>
下面是改進後的版本,利用「只需被已知質數整除」的特性,計算效率有所提升:
<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>個:(計算耗時" + time + "秒)<br>" + str;
output.innerHTML = str;
} else {
output.innerHTML = "<var>請輸入素數的范圍</var>";
}
}
function arrToString(arr) { return arr.join(" "); }
function getPrime2(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>
第一版用篩法反覆劃去倍數;第二版則在判斷每個數時,只用已找到的質數去試除,減少了不必要的取模運算,因此更快。兩個版本都會統計並顯示計算耗時,方便直觀比較效率。