DIV CSS 佈局教程網

用 JavaScript 找出 n 以內的完全數
編輯:JavaScript綜合知識     

完全數(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 需為質數),直接代入會比暴力搜尋快上非常多。這也解釋了為什麼目前已知的完全數全都是偶數,奇完全數是否存在仍是未解難題。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved