完全數:所有真因數(不含自身的約數)之和等於自身的自然數。
目前已知 51 個完全數,皆為偶數,形式為 2^(p-1) × (2^p - 1),其中 2^p - 1 為梅森質數。
function findPerfectNumbers(limit) {
const result = [];
for (let n = 2; n <= limit; n++) {
let sum = 1; // 1 是所有數的因數
for (let i = 2; i * i <= n; i++) {
if (n % i === 0) {
sum += i;
const pair = n / i;
if (pair !== i) sum += pair; // 避免平方數重複
}
}
if (sum === n) result.push(n);
}
return result;
}
// 已知梅森質數指數 p(截至 2024 年前 15 個)
const mersenneExponents = [2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279];
function generatePerfectNumbers(limit) {
const result = [];
for (const p of mersenneExponents) {
const mersenne = (1n << BigInt(p)) - 1n; // 2^p - 1
const perfect = (1n << BigInt(p - 1)) * mersenne; // 2^(p-1) * (2^p - 1)
if (perfect > limit) break;
result.push(Number(perfect));
}
return result;
}
console.log(generatePerfectNumbers(10000)); // [6, 28, 496, 8128]
$('#calc').click(function() {
const limit = parseInt($('#num').val());
if (isNaN(limit) || limit < 2) {
$('#result').text('請輸入大於 1 的整數');
return;
}
const start = performance.now();
const perfects = generatePerfectNumbers(limit);
const elapsed = (performance.now() - start).toFixed(2);
$('#result').html(
perfects.length
? `完全數: ${perfects.join(', ')} (耗時 ${elapsed}ms)`
: `範圍內無完全數 (耗時 ${elapsed}ms)`
);
});
| 方法 | 複雜度 | 適用場景 |
|---|---|---|
| 遍歷 1..n/2 | O(N²) | 教學示範、極小 N |
| 遍歷 2..√n 配對 | O(N√N) | 通用單次查找 |
| 篩法預計算最小質因子 | O(N log log N) | 多次查詢、大範圍 |
| 歐幾里得-歐拉定理 | O(k) | 直接生成完全數、極大範圍 |
截至 2024 年,未發現任何奇完全數。數學家證明若存在,必須:
尋找完全數是理解因數性質、優化迴圈、應用數學定理的絕佳練習。實務中:小範圍用 √n 配對法,大範圍直接套用歐幾里得-歐拉定理。前端展示時注意 `BigInt` 相容性,並善用 `performance.now()` 測量效能,體驗算法優化帶來的數量級提升。