试除法能否判定质数，AcWing 866 的方法靠谱吗？
- 内容介绍
- 文章标签
- 相关推荐
本文共计497个文字，预计阅读时间需要2分钟。
题目：判断质数给定：$n$ 个正整数 $a_i$任务：判断每个数是否是质数。输入格式：第一行包含一个整数 $n$。接下来 $n$ 行，每行包含一个整数 $a_i$。输出格式：共 $n$ 行，每行输出一个判断结果。其中第 $i$ 行输出第 $i$ 个整数是否是质数的结果，格式为：第 $i$ 个正整数是质数 或 第 $i$ 个正整数不是质数。
题目
给定 $n$ 个正整数 $a_i $，判定每个数是否是质数。
输入格式 第一行包含整数 $n$。
接下来 $n$ 行，每行包含一个正整数 $a_i$。
输出格式
共 $n$ 行，其中第 $i$ 行输出第 $i$ 个正整数 $a_i$ 是否为质数，是则输出 Yes，否则输出 No。
数据范围 $1≤n≤100,1≤a_i≤2^{31}−1$ 输入样例：
2
2
6
输出样例：
Yes
No
思路
- 为什么可以遍历$2...x^{1/2}$来确认 对于某个数 $x$，$1、x$为一对因数，我们可以用没对因数的左点i，可以同时验证一对因数。最小的一对左部因数必然 $<= x^{1/2}$，否则两个因数乘积大于 $x$
- 为什么不用 $i * i <= x$ 而是 $i <= x / i$ $i * i <= x$情况下，当x接近类型最大值max时，若$i * i <= max, (i + 1) * (i + 1) > max$，此时数值溢出，会影响对结果的判断
代码
#include <iostream>
using namespace std;
int n, a;
bool is_prime(int x)
{
if (x < 2) return false;
for (int i = 2; i <= x / i; i ++ )
if (x % i == 0) return false;
return true;
}
int main()
{
cin >> n;
while (n -- )
{
cin >> a;
if (is_prime(a)) puts("Yes");
else puts("No");
}
return 0;
}
本文共计497个文字，预计阅读时间需要2分钟。
题目：判断质数给定：$n$ 个正整数 $a_i$任务：判断每个数是否是质数。输入格式：第一行包含一个整数 $n$。接下来 $n$ 行，每行包含一个整数 $a_i$。输出格式：共 $n$ 行，每行输出一个判断结果。其中第 $i$ 行输出第 $i$ 个整数是否是质数的结果，格式为：第 $i$ 个正整数是质数 或 第 $i$ 个正整数不是质数。
题目
给定 $n$ 个正整数 $a_i $，判定每个数是否是质数。
输入格式 第一行包含整数 $n$。
接下来 $n$ 行，每行包含一个正整数 $a_i$。
输出格式
共 $n$ 行，其中第 $i$ 行输出第 $i$ 个正整数 $a_i$ 是否为质数，是则输出 Yes，否则输出 No。
数据范围 $1≤n≤100,1≤a_i≤2^{31}−1$ 输入样例：
2
2
6
输出样例：
Yes
No
思路
- 为什么可以遍历$2...x^{1/2}$来确认 对于某个数 $x$，$1、x$为一对因数，我们可以用没对因数的左点i，可以同时验证一对因数。最小的一对左部因数必然 $<= x^{1/2}$，否则两个因数乘积大于 $x$
- 为什么不用 $i * i <= x$ 而是 $i <= x / i$ $i * i <= x$情况下，当x接近类型最大值max时，若$i * i <= max, (i + 1) * (i + 1) > max$，此时数值溢出，会影响对结果的判断
代码
#include <iostream>
using namespace std;
int n, a;
bool is_prime(int x)
{
if (x < 2) return false;
for (int i = 2; i <= x / i; i ++ )
if (x % i == 0) return false;
return true;
}
int main()
{
cin >> n;
while (n -- )
{
cin >> a;
if (is_prime(a)) puts("Yes");
else puts("No");
}
return 0;
}