中等 · 嵌套循环
数素数个数
n 以内有多少个素数?第一道“内层循环才是主角”的题——也是 break 第一次成为性能问题而不只是风格。
题目
输入:一个整数 n(0 ≤ n ≤ 10⁶)。
输出:满足 p ≤ n 的素数 p 的个数。
样例:
| 输入 | 输出 |
|---|---|
10 | 4 |
100 | 25 |
你的解答
"用我的输入试跑"的自定义输入
判题完全在你的浏览器里对隐藏测试运行。代码随打随存(本地)。Ctrl+Enter 判题。
卡住了?提示
提示 1 —— 复用素数判定
内层判断就是素数判定那道题:试除到 √i,找到第一个因子就 break。外面套一层 2..n 的循环,数幸存者。
提示 2 —— break 为什么重要
不写 break,每个数都要试完所有因子;写了,大多数数除一两次就退出。n = 10⁶ 时这是"秒级"和"超时"的差别。
解答(先自己试!)
int n = int.Parse(Console.ReadLine());
int count = 0;
for (int i = 2; i <= n; i++)
{
bool prime = true;
for (int d = 2; d * d <= i; d++)
{
if (i % d == 0) { prime = false; break; }
}
if (prime) count++;
}
Console.WriteLine(count);再进一步是埃拉托色尼筛法——用布尔数组代替试除,把 O(n√n) 变成 O(n log log n)。下一题:水仙花数。