题解 | #筛法判断质数#
筛法判断质数
https://www.nowcoder.com/practice/8afab457ef11456d8602ce6dc30db776
题目链接
题目描述
给定 T 个正整数，对于每个正整数 x，请判断它是否为质数。
- 若
x是质数，输出 "Yes"。 - 若
x不是质数，输出 "No"。
【名词解释】质数（或素数）：在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。
解题思路
当需要对多个数进行质数判断时，为每个数单独使用试除法会很慢。一个更高效的策略是先预处理，用筛法一次性找出某个范围内的所有质数，然后对于每个查询，直接查表即可。埃拉托斯特尼筛法（Sieve of Eratosthenes）是实现这一目标的经典算法。
-
算法原理：
- 我们创建一个布尔数组
is_prime，大小为N+1（N是题目中x的最大可能值，如10^6），并初始化所有值为true，表示我们假设所有数都是质数。 - 我们知道 0 和 1 不是质数，所以手动将
is_prime[0]和is_prime[1]设为false。 - 从第一个质数 2 开始遍历。如果一个数
p仍然被标记为true，那它就是一个质数。 - 对于每个找到的质数
p，我们将它所有的倍数（2*p,3*p,4*p, ...）在数组中标记为false，因为它们必然是合数。
- 我们创建一个布尔数组
-
优化：
- 在标记倍数时，我们可以从
p*p开始。因为任何小于p*p的p的倍数（例如k*p其中k<p），必然有一个更小的质因子k，所以在处理k时就已经被筛掉了。 - 外层循环也只需要遍历到
sqrt(N)即可，因为任何大于sqrt(N)的合数，其最小质因子必然小于sqrt(N)，所以它也一定被筛掉了。
- 在标记倍数时，我们可以从
-
回答查询：
- 筛法执行完毕后，
is_prime数组就成了一张完整的“质数表”。 - 对于之后来的每一个查询
x，我们只需要检查is_prime[x]的值即可，这是一个的操作。
- 筛法执行完毕后，
代码
#include <iostream>
#include <vector>
using namespace std;
const int N_MAX = 1000001;
bool is_prime[N_MAX];
void sieve() {
fill(is_prime, is_prime + N_MAX, true);
is_prime[0] = is_prime[1] = false;
for (int p = 2; p * p < N_MAX; ++p) {
if (is_prime[p]) {
for (int i = p * p; i < N_MAX; i += p) {
is_prime[i] = false;
}
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
sieve();
int t;
cin >> t;
while (t--) {
int x;
cin >> x;
if (is_prime[x]) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
}
return 0;
}
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static final int N_MAX = 1000001;
static boolean[] isPrime = new boolean[N_MAX];
static {
Arrays.fill(isPrime, true);
isPrime[0] = isPrime[1] = false;
for (int p = 2; p * p < N_MAX; p++) {
if (isPrime[p]) {
for (int i = p * p; i < N_MAX; i += p) {
isPrime[i] = false;
}
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while (t-- > 0) {
int x = sc.nextInt();
if (isPrime[x]) {
System.out.println("Yes");
} else {
System.out.println("No");
}
}
}
}
N_MAX = 1000001
is_prime = [True] * N_MAX
is_prime[0] = is_prime[1] = False
# 埃拉托斯特尼筛法
p = 2
while p * p < N_MAX:
if is_prime[p]:
for i in range(p * p, N_MAX, p):
is_prime[i] = False
p += 1
# 读取输入并查询
t = int(input())
for _ in range(t):
x = int(input())
if is_prime[x]:
print("Yes")
else:
print("No")
算法及复杂度
- 算法：埃拉托斯特尼筛法
- 时间复杂度：
。筛法预处理的时间复杂度为
，其中
N是数据上限 (10^6)。之后的T次查询，每次都是 - 空间复杂度：
。需要一个大小为
N的布尔数组来存储质数表。
腾讯开奖369人在聊