萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 腳本程式專題 >> JavaScript

jQuery 尋找 N 以內完全數:因數遍歷優化、效能分析與數學原理深度解析

完全數定義

完全數:所有真因數(不含自身的約數)之和等於自身的自然數。

  • 6 = 1 + 2 + 3
  • 28 = 1 + 2 + 4 + 7 + 14
  • 496 = 1 + 2 + 4 + 8 + 16 + 31 + 62 + 124 + 248
  • 8128 = ...

目前已知 51 個完全數,皆為偶數,形式為 2^(p-1) × (2^p - 1),其中 2^p - 1 為梅森質數。

暴力解法:O(N√N)


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]
  • 時間複雜度:O(k),k 為梅森質數個數(極快)
  • 需 `BigInt` 支援(Node 10.4+、現代瀏覽器)
  • 適用於大範圍查找(如 10^1000 以內)

jQuery 整合版(教學用)


$('#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/2O(N²)教學示範、極小 N
遍歷 2..√n 配對O(N√N)通用單次查找
篩法預計算最小質因子O(N log log N)多次查詢、大範圍
歐幾里得-歐拉定理O(k)直接生成完全數、極大範圍

數學延伸:奇完全數猜想

截至 2024 年,未發現任何奇完全數。數學家證明若存在,必須:

  • 大於 10^1500
  • 至少有 101 個質因子(含重複)
  • 至少 10 個不同質因子
  • 最大質因子 > 10^8

總結

尋找完全數是理解因數性質、優化迴圈、應用數學定理的絕佳練習。實務中:小範圍用 √n 配對法,大範圍直接套用歐幾里得-歐拉定理。前端展示時注意 `BigInt` 相容性,並善用 `performance.now()` 測量效能,體驗算法優化帶來的數量級提升。

copyright © 萬盛學電腦網 all rights reserved