小明刚刚学习了素数的概念:如果一个大于 1 的正整数,除了 1 和它自身外,不能被其他正整数整除,则这个正整数是素数。现在,小明想找到两个正整数 A 和 B 之间(包括 A 和 B)有多少个素数。
小明刚刚学习了素数的概念:如果一个大于 1 的正整数,除了 1 和它自身外,不能被其他正整数整除,则这个正整数是素数。现在,小明想找到两个正整数 A 和 B 之间(包括 A 和 B)有多少个素数。
请参考题目描述中的样例
大于 1 的正整数,除了 1 和自身不能被其他数整除。试除法:枚举 2 到 √n。
bool isPrime(int n) { if (n < 2) return false; for (int i=2; i*i<=n; i++) if (n%i==0) return false; return true; }
读入 a 和 b。
从 a 到 b 逐个判断。
枚举 2 到 √n 检查是否能整除。
是素数则输出。
点"算一下"按钮开始 →
读入 a 和 b。
从 a 到 b 逐个判断。
枚举 2 到 √n 检查是否能整除。
是素数则输出。
#include <iostream> using namespace std; bool isPrime(int n) { if (n < 2) return false; for (int i = 2; i*i <= n; i++) if (n % i == 0) return false; return true; } int main() { int a, b; cin >> a >> b; for (int i = a; i <= b; i++) if (isPrime(i)) cout << i << endl; return 0; }
时间:根据算法结构分析时间复杂度。
空间:只使用少量变量,O(1)。
✅ 在数据范围内轻松通过!
// 嵌套循环遍历矩阵 for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { // 处理 (i, j) } } // 取余判断整除 if (n % k == 0) { ... } // 数位分离 while (n > 0) { d = n % 10; n /= 10; }