freeCodeCamp 每日编程挑战解读:使用 JavaScript 实现 Nth Prime 求解第 n 个质数
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);
从中可以推断两个关键约束:
- 测试覆盖到
n = 1000,意味着算法至少需要在合理时间内找到第 1000 个质数(7919),规模不大但要求实现正确。 - 选手在挑战中会得到一个空壳函数(
# --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];
}
逐行理解如下:
const primes = []:用数组按顺序缓存已找到的质数,最终长度将达到n。let num = 2:候选数从2开始递增。从 1 或 0 开始都没有意义(不符合质数定义),从 2 开始则天然覆盖了第一个质数。while (primes.length < n):外层循环的终止条件。每找到一个质数就push一次,当数组长度达到n时循环自然结束。let isPrime = true:每轮先假设num是质数,再在下面的内层循环中尝试推翻它。for (let i = 2; i * i <= num; i++):内层循环以i * i <= num作为上界,等价于i <= sqrt(num),避免了每次迭代调用Math.sqrt的开销。一旦发现整除就isPrime = false; break;提前退出,属于短路判定。if (isPrime) primes.push(num);:只有完全没被整除的num才被记为质数。num++:无论是否质数,都递增候选数,继续下一轮判定。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。