1 条题解
-
0
区间素数统计 题解
思路概述
本题考察双重嵌套循环(Nested Loops)的使用与标志位控制:
- 外层循环:遍历数字 。
- 内层循环:判断数字 是否为质数。 枚举可能的因子 。如果存在某个 满足 ,说明 是合数,直接跳出内层循环;若没有找到任何因子,则说明 是质数,计数器加 1。
参考代码如下:
int count = 0; for (int i = 2; i <= n; i++) { bool is_prime = true; for (int j = 2; j * j <= i; j++) { if (i % j == 0) { is_prime = false; break; } } if (is_prime) { count++; } } cout << count << "\n";正确性说明
由质数试除法原理,若 为合数,必存在小于等于 的质因子,因此试除到 即可完全覆盖。
复杂度分析
- 时间复杂度:外层循环执行 次,内层试除至多 次。总时间复杂度为 。当 时,计算量大约为 次基本操作,运行时间远低于 1 秒。
- 空间复杂度:。
- 1
信息
- ID
- 121
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 2
- 标签
- 递交数
- 2
- 已通过
- 1
- 上传者