测试截至 sqrt(n) 的素性
高效检查单个数字
测试截至 sqrt(n) 的素性 是 CoddyKit 上的免费 Competitive Programming Academy 课时。 这是第 2 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Competitive Programming Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Competitive Programming Academy 课程共包含 4 节课。
质数问题
判断一个数是否为质数是一项基础数学技能。质数恰好有两个因数：1 和它本身。让我们快速进行判断。🔍
朴素检查
您可以尝试让 n 除以从 2 到 n 减 1 的每个数。这种方法虽然正确，但当 n 很大时会慢得令人难以忍受。
平方根技巧
关键在于：您只需要测试直到 n 的平方根为止的因数。超过这个范围后，不会出现新的因数。
为什么平方根就够了
因数会成对出现，它们的乘积等于 n。如果两个因数都大于平方根，它们的乘积就会超过 n，这是不可能的。
循环边界
只要 i 乘以 i 不超过 n，就从 2 开始递增 i。使用 i*i 可以避免对大整数使用 sqrt 时产生浮点误差。
while i * i <= n:
...处理较小的情况
小于 2 的数都不是质数，因此请一开始就排除它们。这个保护条件可以让主循环保持简洁且正确。
if n < 2:
return False完整函数
将它们组合起来：先处理较小的值，然后扫描直到平方根范围内的可能因数。只要能够整除 n，就说明 n 是合数。
def is_prime(n):
if n < 2:
return False
i = 2
while i * i <= n:
if n % i == 0:
return False
i += 1
return True进一步提速
单独检查 2，然后只测试奇数。跳过偶数不会增加额外复杂度，却能让工作量大约减少一半。
if n % 2 == 0:
return n == 2时间开销
该检查的时间复杂度为 O(sqrt n)。对于不超过十亿的单个数，这只需要大约 30,000 次简单操作。
一个数，而不是许多数
平方根检查适合一个或少量查询。如果您需要判断整个范围内的质数，筛法会快得多。
避免平方根陷阱
使用 i*i 而不是 math.sqrt 进行比较，可以避开舍入误差，防止错误地接受或拒绝临界值。
快速检查
确认一下让这种检查变快的边界。
回顾
现在您可以在 O(sqrt n) 时间内判断一个数是否为质数，处理较小的值，跳过偶数，并使用 i*i 保证精确性。✅
常见问题解答
「测试截至 sqrt(n) 的素性」课时是免费的吗？
是的 — 「测试截至 sqrt(n) 的素性」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Competitive Programming Academy 课程的其余内容，请升级到 CoddyKit PRO。 Competitive Programming Academy 课程共包含 4 节课。
「测试截至 sqrt(n) 的素性」这节课中我会学到什么？
高效检查单个数字 你通过在浏览器中直接运行的动手代码来练习 Competitive Programming Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Competitive Programming Academy 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Competitive Programming Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 2 节课，共 4 节。
「测试截至 sqrt(n) 的素性」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Competitive Programming Academy 课中编写并运行代码吗？
能。每节 Competitive Programming Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- GCD、LCM 与欧几里得算法
- 测试截至 sqrt(n) 的素性
- 埃拉托斯特尼筛法
- 质因数分解与因数