P1201 练33.2 素数判断
小于 1 分钟
P1201 练33.2 素数判断
【算法】 素数判断
【C++】 循环、取模、sqrt
【难度】 入门
一、题目简述
输入一个自然数,判断是否为素数。素数:大于 1 且因数只有 1 和它本身的数。1 既不是素数也不是合数。
二、解题思路
试除法:若 ,直接输出 N。否则从 2 枚举到 ,如果 能被任何一个数整除,则不是素数。
为什么到 ?因为如果 有一个大于 的因数,必定有一个小于 的因数与之对应。
三、参考代码
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
if (n <= 1) {
cout << "N" << endl;
return 0;
}
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
cout << "N" << endl;
return 0;
}
}
cout << "Y" << endl;
return 0;
}四、复杂度分析
- 时间:,对于单个数的判断非常快。
- 空间:。
五、易错点
- 1 不是素数:特判
n <= 1。 - 循环从 2 开始,不是从 1。
- 判断条件
i * i <= n比i <= sqrt(n)更好,避免浮点误差。
