freeCodeCamp 每日编程挑战解读:使用 JavaScript 实现 Nth Prime 求解第 n 个质数

原创2026-09-08 17:00:521,853 阅读
文章标签:教育前端后端教程关系型数据库国际化

freeCodeCamp 每日编程挑战解读:使用 JavaScript 实现 Nth Prime 求解第 n 个质数

本篇技术指南聚焦 freeCodeCamp 开源仓库中 daily-coding-challenges-javascript 模块的 Challenge 81: Nth Prime(挑战原文),完整拆解题目定义、验证用例、官方参考解法及其背后的试除法(trial division)原理。读完本文,你将掌握质数判定的核心算法、如何以 sqrt(n) 为界高效剪枝,以及这一类「按序生成质数」问题的扩展优化路径。

题目背景:每日编程挑战系列中的 Challenge 81

Nth Prime 是 freeCodeCamp JavaScript 每日编程挑战(Daily Coding Challenge)序列中的第 81 道题。该序列与 Python 序列一一配对,每个题目在 JavaScript 与 Python 两种语言下共享相同的题目 ID、标题、描述与测试条数,这一对称性由 curriculum/src/test/daily-challenges.test.js 中的测试用例强制保证——它逐条比对两种语言挑战的 id、title、description 与测试数量,任何不匹配都会直接断言失败。

从挑战所属的区块配置文件 curriculum/structure/blocks/daily-coding-challenges-javascript.json 可以看到该系列的工程化设定:

{
  "isUpcomingChange": true,
  "dashedName": "daily-coding-challenges-javascript",
  "usesMultifileEditor": true,
  "helpCategory": "JavaScript",
  "disableLoopProtectTests": true,
  "blockLayout": "legacy-challenge-list"
}

其中 helpCategory 为 JavaScript、usesMultifileEditor 为 true,说明学习者将在多文件编辑器中直接编写并运行函数。本挑战在 packages/shared/src/config/challenge-types.ts 中被标记为编号 28 的 dailyChallengeJs 类型(Python 版为 29),并可通过其 getIsDailyCodingChallenge 帮助函数识别。客户端还会用 client/src/utils/daily-coding-challenge-validator.ts 中的 Joi 模式校验这类挑战的 tests(每条包含 text 与 testString)与 challengeFiles 结构。

题目描述:什么是「第 n 个质数」

题目原文给出了质数的精确定义:

质数是大于 1 且只能被 1 和自身整除的正整数。前五个质数是 2、3、5、7、11。

给定一个正整数 n,返回第 n 个质数。例如给定 5,应返回第 5 个质数:11。

需要特别注意两条边界信息:

  • 1 不是质数:质数的定义从 2 开始,因此第 1 个质数是 2,而不是 1。
  • 2 是唯一的偶质数:它是质数序列的起点,也是判定与生成算法中不可跳过的初始值。

解题目标非常清晰:不给定上限,而是给定序号 n,要求生成质数序列 2, 3, 5, 7, 11, ... 并取出第 n 个。这与常见的「找出不超过 N 的所有质数」不同,属于按需生成、序号驱动型问题。

验证用例:5 组断言构成的可执行规格

题目通过 5 组 assert.equal 断言定义了精确的输入输出规格(位于挑战文件的 # --hints-- 区段),它们是评判答案的唯一标准:

调用 期望返回值 含义
nthPrime(5) 11 前 5 个质数 2, 3, 5, 7, 11 中的第 5 个
nthPrime(10) 29 第 10 个质数
nthPrime(16) 53 第 16 个质数
nthPrime(99) 523 第 99 个质数
nthPrime(1000) 7919 第 1000 个质数

这些断言的原始形式如下:

assert.equal(nthPrime(5), 11);
assert.equal(nthPrime(10), 29);
assert.equal(nthPrime(16), 53);
assert.equal(nthPrime(99), 523);
assert.equal(nthPrime(1000), 7919);

从中可以推断两个关键约束:

  1. 测试覆盖到 n = 1000,意味着算法至少需要在合理时间内找到第 1000 个质数(7919),规模不大但要求实现正确。
  2. 选手在挑战中会得到一个空壳函数(# --seed-contents-- 段),必须填充函数体:
function nthPrime(n) {

  return n;
}

初始实现直接返回 n,只对极少数输入成立,几乎全部断言都会失败,因此必须完整实现质数生成逻辑。

核心思路一:单数判定的试除法

最简单直接的方法是逐个自然数判断是否为质数。根据质数定义,一个数 num 是质数,当且仅当它在 [2, num - 1] 区间内没有任何因子。

朴素写法如下:

function isPrime(num) {
  if (num < 2) return false;
  for (let i = 2; i < num; i++) {
    if (num % i === 0) return false;
  }
  return true;
}

这种实现的时间复杂度为 O(num)(对单个候选数)。但存在一个非常关键的可优化点:如果 num 有大于 sqrt(num) 的因子,那么它必然同时有一个小于 sqrt(num) 的因子与之配对。例如判定 36,因子对是 (2, 18)、(3, 12)、(4, 9)、(6, 6)——每对中至少一个因子不超过 6 = sqrt(36)。

因此,只需要检查 i * i <= num 即可,即把遍历上界从 num 压缩到 sqrt(num),这是该题最重要的性能优化,也是官方解法采用的策略。

核心思路二:官方参考解法的逐行拆解

挑战文件 # --solutions-- 区段给出了 freeCodeCamp 认可的参考实现,其核心是「边扫描边收集已确认质数,直至收集满 n 个」:

function nthPrime(n) {
  const primes = [];
  let num = 2;

  while (primes.length < n) {
    let isPrime = true;
    for (let i = 2; i * i <= num; i++) {
      if (num % i === 0) {
        isPrime = false;
        break;
      }
    }
    if (isPrime) primes.push(num);
    num++;
  }

  return primes[n - 1];
}

逐行理解如下:

  1. const primes = []:用数组按顺序缓存已找到的质数,最终长度将达到 n。
  2. let num = 2:候选数从 2 开始递增。从 1 或 0 开始都没有意义(不符合质数定义),从 2 开始则天然覆盖了第一个质数。
  3. while (primes.length < n):外层循环的终止条件。每找到一个质数就 push 一次,当数组长度达到 n 时循环自然结束。
  4. let isPrime = true:每轮先假设 num 是质数,再在下面的内层循环中尝试推翻它。
  5. for (let i = 2; i * i <= num; i++):内层循环以 i * i <= num 作为上界,等价于 i <= sqrt(num),避免了每次迭代调用 Math.sqrt 的开销。一旦发现整除就 isPrime = false; break; 提前退出,属于短路判定。
  6. if (isPrime) primes.push(num);:只有完全没被整除的 num 才被记为质数。
  7. num++:无论是否质数,都递增候选数,继续下一轮判定。
  8. return primes[n - 1];:因为数组是 0 索引的,第 n 个质数存放在 primes[n - 1]。

用官方测试逐例验证

  • n = 5:收集到 [2, 3, 5, 7, 11] 后 primes.length === 5,循环停止,返回 primes[4] === 11 ✔
  • n = 10:序列继续到 29,返回 primes[9] === 29 ✔
  • n = 16:返回 primes[15] === 53 ✔
  • n = 99:返回 primes[98] === 523 ✔
  • n = 1000:返回 primes[999] === 7919 ✔

复杂度分析

官方解法对每个候选数做一次 O(sqrt(num)) 的试除。质数的分布密度约为 n / ln(n)(质数定理),因此要找到第 n 个质数大约需要检查 n · ln(n) 量级的候选数。对题目的最大输入 n = 1000(第 1000 个质数为 7919,需检查约 7919 个候选数),总体代价约为 Σ sqrt(k),完全在毫秒级内完成,足够通过全部断言。

边界情况与易错点

这是本类题目最常见的出错点,务必在实现前想清楚:

场景 正确行为 常见错误
n = 1 返回 2(第一个质数) 返回 1
num = 2 内层循环 2 * 2 <= 2 为假,直接判定质数 误判为合数
num = 4 2 * 2 <= 4,4 % 2 === 0,立即判为合数 漏判平方数因子
大 n 内层循环上界用 sqrt(num) 用 num - 1 导致平方级退化

特别地,num = 2 时内层循环条件 i * i <= num 即 4 <= 2 为假,循环体一次都不执行,isPrime 保持 true,从而正确地将 2 收入质数数组——这正是官方解法无需为 2 单独写 if 分支的原因。

扩展优化:埃拉托斯特尼筛法与预生成策略

虽然官方解法已经足够通过本题,但作为算法练习,可以从两个方向继续演进:

方案一:只与已知质数相除

试除时无需遍历所有小于 sqrt(num) 的整数,只需要除以前面已经收集到的质数(因为合数因子必然能被更小的质数分解):

function nthPrime(n) {
  const primes = [2];
  for (let num = 3; primes.length < n; num += 2) {
    const isPrime = primes.every(
      p => p * p > num || num % p !== 0
    );
    if (isPrime) primes.push(num);
  }
  return primes[n - 1];
}

由于所有偶数(除 2 外)都不可能是质数,还可以让候选数 num 只递增奇数(num += 2),将需判定的候选数再砍半。

方案二:埃拉托斯特尼筛法(Sieve of Eratosthenes)

如果需要一次性得到大量质数,可先借助质数定理估算上限 limit(例如 n · (ln n + ln ln n)),再用筛法批量标记:

function sieve(limit) {
  const isPrime = new Array(limit + 1).fill(true);
  isPrime[0] = isPrime[1] = false;
  for (let i = 2; i * i <= limit; i++) {
    if (isPrime[i]) {
      for (let j = i * i; j <= limit; j += i) isPrime[j] = false;
    }
  }
  return isPrime;
}

筛法的时间复杂度约为 O(limit · log log limit),在大 n 场景下远优于逐数试除。但需要注意,它对内存有线性需求,且需要预先估计上界;若估计过小还得扩容重筛,实现复杂度高于试除法。对本题 n <= 1000 的量级,官方试除法在简洁性与性能上已取得最佳平衡。

总结

Nth Prime(Challenge 81)是一道典型的序号驱动的质数生成问题:它在 [2, 1000] 范围内定义了明确的输入输出契约,官方参考解法用「外层按序扫描候选数 + 内层以 sqrt(num) 为界的试除」这一经典组合完成求解,代码量小但覆盖了质数判定、循环上界剪枝、数组索引等关键编程点。理解它的解法,不仅能通过 freeCodeCamp 的全部 5 条断言,也为后续阅读该系列其余挑战(如 Challenge 13 Unnatural Prime、Challenge 152 Circular Prime、Challenge 138 Sum of Divisors 等同属质数主题的题目)打下坚实基础。若想在本地复现与验证,可继续阅读同一区块内其余挑战的 Markdown 文件(存放于 curriculum/challenges/english/blocks/daily-coding-challenges-javascript),以及维护 JS/Python 双语言挑战一致性的测试 curriculum/src/test/daily-challenges.test.js。

登录后查看全文
freeCodeCamp