PTA 天梯赛 L1-028 判断素数 (10 point(s))

L1-028 判断素数 (10 point(s))

本题的目标很简单，就是判断一个给定的正整数是否素数。

输入格式：

输入在第一行给出一个正整数N（≤ 10），随后N行，每行给出一个小于2^​31 ​​ 的需要判断的正整数。

输出格式：

对每个需要判断的正整数，如果它是素数，则在一行中输出Yes，否则输出No。

输入样例：

2 11 111

输出样例：

Yes No

思路：

简单的判断素数的题目，但是本题很卡时间，所以必须用sqrt也就是根号的意思这样可以大大缩短时间复杂度。

#include <iostream> #include <cmath> using namespace std; bool isprime(int n) { if(n == 0 || n == 1) return false; for (int i = 2; i <= sqrt(n); i++){ if (n % i == 0) return false; } return true; } int main() { int n, m, num; cin >> n; while (n--) { cin >> m; if (isprime(m)) cout << "Yes\n"; else cout << "No\n"; } return 0; }