JS最优数字回文验证方案及五位数质数乘积最大回文求解

我来帮你拆解下当前程序的性能瓶颈，然后给出几个能大幅提升运行速度的优化方向——核心是彻底避免字符串转换，同时优化质数遍历逻辑，减少无效计算：

一、用纯数字运算替代字符串回文验证 #

你提到数字转字符串的操作耗时最高，那咱们直接绕开字符串，用取模、除法这些数字运算来判断回文，速度会快很多，而且只需要反转一半数字就可以完成判断：

function isPalindrome(num) {
  // 五位数质数的乘积不可能是0，结尾为0的数也不可能是回文（开头得是0），直接排除
  if (num % 10 === 0) return false;
  let reversedHalf = 0;
  // 只反转一半数字，比全反转更高效
  while (num > reversedHalf) {
    reversedHalf = reversedHalf * 10 + num % 10;
    num = Math.floor(num / 10);
  }
  // 偶数长度：原数的一半等于反转后的数；奇数长度：反转数去掉最后一位等于原数的一半
  return num === reversedHalf || num === Math.floor(reversedHalf / 10);
}

这个函数完全没有字符串操作，所有逻辑都是数字运算，比你之前的字符串版本快至少几倍。

二、优化质数判断和生成逻辑 #

你的isPrime函数之前循环到number/2，这会做很多无效判断，我们可以优化成循环到平方根，同时利用质数的特性（大于3的质数都在6n±1的形式里）来减少循环次数：

function isPrime(number) {
  if (number <= 1) return false;
  if (number <= 3) return true;
  // 先排除偶数和3的倍数，减少后续循环次数
  if (number % 2 === 0 || number % 3 === 0) return false;
  let i = 5;
  const sqrtNum = Math.sqrt(number);
  // 只检查6n±1的数，因为其他数都能被2或3整除
  while (i <= sqrtNum) {
    if (number % i === 0 || number % (i + 2) === 0) return false;
    i += 6;
  }
  return true;
}

function get5DigitPrimeNr() {
  const primes = [];
  // 五位数从10000开始，但10000是偶数，直接从10001开始，跳过所有偶数
  for (let i = 10001; i < 100000; i += 2) {
    if (isPrime(i)) primes.push(i);
  }
  return primes;
}

这里get5DigitPrimeNr直接跳过偶数，减少了一半的循环次数，进一步提升质数生成的速度。

三、优化遍历逻辑，减少无效计算 #

你之前的双重循环遍历所有质数组合，会做大量重复计算和无效判断，我们可以从大到小遍历，一旦找到符合条件的回文数就提前终止：

function runme() {
  const primes = get5DigitPrimeNr();
  const len = primes.length;
  let maxPalindrome = 0;
  let resultMsg = "";
  
  // 从最大的质数开始遍历，优先检查大的乘积
  for (let i = len - 1; i >= 0; i--) {
    const primeA = primes[i];
    // 如果当前质数的平方已经小于已找到的最大回文，后面的乘积只会更小，直接终止外层循环
    if (primeA * primeA < maxPalindrome) break;
    
    // 只遍历到i，避免重复计算（primeA*primeB 和 primeB*primeA 结果相同）
    for (let j = i; j >= 0; j--) {
      const product = primeA * primes[j];
      // 如果当前乘积已经小于已找到的最大回文，更小的j乘积只会更小，直接终止内层循环
      if (product <= maxPalindrome) break;
      if (isPalindrome(product)) {
        maxPalindrome = product;
        resultMsg = `最大回文数: ${maxPalindrome}, 由 ${primeA} × ${primes[j]} 得到`;
        // 因为是从大到小找，找到第一个符合条件的就可以跳出内层循环
        break;
      }
    }
  }
  console.log(resultMsg);
}

这个逻辑的核心是尽早终止无效循环：一旦当前质数的平方都小于已找到的最大回文，后面的所有乘积都不可能更大，直接停止遍历；内层循环同理，乘积小于当前最大值就直接跳过。

完整优化后的代码 #

把上面的函数整合起来，再保留你的计时函数：

function isPrime(number) {
  if (number <= 1) return false;
  if (number <= 3) return true;
  if (number % 2 === 0 || number % 3 === 0) return false;
  let i = 5;
  const sqrtNum = Math.sqrt(number);
  while (i <= sqrtNum) {
    if (number % i === 0 || number % (i + 2) === 0) return false;
    i += 6;
  }
  return true;
}

function get5DigitPrimeNr() {
  const primes = [];
  for (let i = 10001; i < 100000; i += 2) {
    if (isPrime(i)) primes.push(i);
  }
  return primes;
}

function isPalindrome(num) {
  if (num % 10 === 0) return false;
  let reversedHalf = 0;
  while (num > reversedHalf) {
    reversedHalf = reversedHalf * 10 + num % 10;
    num = Math.floor(num / 10);
  }
  return num === reversedHalf || num === Math.floor(reversedHalf / 10);
}

function runme() {
  const primes = get5DigitPrimeNr();
  const len = primes.length;
  let maxPalindrome = 0;
  let resultMsg = "";
  
  for (let i = len - 1; i >= 0; i--) {
    const primeA = primes[i];
    if (primeA * primeA < maxPalindrome) break;
    
    for (let j = i; j >= 0; j--) {
      const product = primeA * primes[j];
      if (product <= maxPalindrome) break;
      if (isPalindrome(product)) {
        maxPalindrome = product;
        resultMsg = `最大回文数: ${maxPalindrome}, 由 ${primeA} × ${primes[j]} 得到`;
        break;
      }
    }
  }
  console.log(resultMsg);
}

function timeMe() {
  const t0 = performance.now();
  runme();
  const t1 = performance.now();
  console.log(`函数耗时 ${millisToMinutesAndSeconds(t1 - t0)} 秒找到最大回文数。`);
}

function millisToMinutesAndSeconds(millis) {
  const minutes = Math.floor(millis / 60000);
  const seconds = ((millis % 60000) / 1000).toFixed(0);
  return `${minutes}:${seconds < 10 ? '0' : ''}${seconds}`;
}

这些优化应该能让你的程序运行速度提升几十倍甚至上百倍，尤其是回文验证部分的性能提升最明显。

内容的提问来源于stack exchange，提问作者tzim