中等 · 试除法
素数判定
n 有没有 1 和自身之外的因子?只试到 √n——而且找到一个就停。√n 这个界正是它快的原因。
题目
输入:一个整数 n(0 ≤ n ≤ 10⁶)。
输出:素数输出 Yes,否则 No(0 和 1 不是素数)。
样例:
| 输入 | 输出 |
|---|---|
7 | Yes |
25 | No |
你的解答
"用我的输入试跑"的自定义输入
判题完全在你的浏览器里对隐藏测试运行。代码随打随存(本地)。Ctrl+Enter 判题。
卡住了?提示
提示 1 —— 为什么 √n 就够
如果 n = a × b 且 a ≤ b,那么 a ≤ √n。大于 √n 的因子总配着一个更小的——所以试到 i * i <= n 就覆盖全部。
提示 2 —— 边界情况
n < 2 → 不是素数(循环之前处理)。25 这样的完全平方数需要 i * i <= n 里的 <=,不是 <——否则 5×5 溜过去。找到因子立刻 break。
解答(先自己试!)
int n = int.Parse(Console.ReadLine());
if (n < 2) { Console.WriteLine("No"); return; }
bool prime = true;
for (int i = 2; i * i <= n; i++)
{
if (n % i == 0) { prime = false; break; }
}
Console.WriteLine(prime ? "Yes" : "No");顶层的 return 提前离场——n < 2 的情况不需要 else。把它扩到“数出 N 以内全部素数”就是筛法——很好的下一站。下一题:斐波那契数。