完全數(Perfect Number)指的是「所有真因數之和恰好等於自身的數」。它同時是最稀有、數論中最迷人的一類整數。本文示範如何在瀏覽器中找出指定範圍內的所有完全數。
一個數的「完滿程度」取決於它的因數(能整除它的那些數)。例如 12 的因數是 1、2、3、4、6,加總為 16,大於 12 本身,因此 12 稱為「盈數」。反之,10 的因數 1、2、5 加總只有 8,小於 10,稱為「虧數」。
而因數總和恰好等於自身的數,就是完全數——例如 6(1+2+3)、28、496、8128。摘自《費馬大定理》的說法:「最有意義和最少見的數,是那些其因數之和恰好等於其本身的數。」
若整數 n 除以 m 的結果是無餘數的整數,則 m 是 n 的因數。注意唯有被除數、除數、商皆為整數且餘數為零時,這層關係才成立;反過來說,n 就是 m 的倍數。
<!DOCTYPE html> <html> <head> <meta charset="utf-8"> <title>JS Bin</title> </head> <body> <input type="text" id="num" /> <button id="calc">計算</button> <p id="result"></p> </body> </html>
/* 尋找 n 以內的完全數 */
function $(id) {
return document.getElementById(id);
}
// 判斷是否為正整數
function isIntNum(number) {
var num = number;
if ((!isNaN(num)) && (parseInt(num) == parseFloat(num))) {
return true;
} else {
return false;
}
}
$("calc").addEventListener("click", function () {
var inputNum = $("num").value,
$result = $("result"),
factorArr = [],
resultArr = [],
i = 0, sum = 0;
// 先驗證輸入
if (isIntNum(inputNum)) {
console.log("right");
} else {
$result.innerHTML = "輸入錯誤:請輸入正整數";
return false;
}
// 逐一檢驗每個數字
for (var k = 1; k < inputNum; k++) {
factorArr.length = 0; // 每輪重置
sum = 0;
// 尋找因數:只需走到 k/2 即可
for (i = 1; i < Math.floor(k / 2) + 1; i++) {
if (k % i === 0) {
factorArr.push(i);
}
}
// 累加因數
for (var m = 0; m < factorArr.length; m++) {
sum += factorArr[m];
}
// 因數總和等於自身即為完全數
if (sum === k) {
resultArr.push(k);
}
}
$result.innerHTML = resultArr;
});
上述寫法對每個 k 都從 1 掃到 k/2,整體複雜度約為 O(n²)。若輸入值很大,可以只掃到 Math.sqrt(k),並把找到的配對因數同時加入,即可降到 O(√k)。另外,偶數完全數有 2^(p-1) × (2^p − 1) 這樣的歐拉公式(其中 2^p − 1 需為質數),直接代入會比暴力搜尋快上非常多。這也解釋了為什麼目前已知的完全數全都是偶數,奇完全數是否存在仍是未解難題。