题解 | #素数对#
素数对
https://www.nowcoder.com/practice/9aaa288943e7498a9626d4f4f12ced4c
题目链接
题目描述
给定一个正整数 N，请计算有多少个有序素数三元组 (p1, p2, p3) 满足以下条件：
p1, p2, p3都是素数。p1, p2, p3 <= N。p1 + p2 = p3^2。
解题思路
这是一个计数问题，直接暴力搜索所有素数组合 (p1, p2, p3) 会非常慢。我们需要通过数论的性质来优化。
1. 奇偶性分析
我们来分析 p1 + p2 = p3^2 这个核心等式。
-
质数中只有一个偶数：2。其他所有质数都是奇数。
-
情况一：
p1和p2都是奇素数。奇数 + 奇数 = 偶数。- 那么
p3^2必须是偶数，这意味着p3也必须是偶数。 - 唯一的偶素数是 2，所以
p3 = 2。 - 等式变为
p1 + p2 = 2^2 = 4。 - 是否存在两个奇素数
p1, p2，它们的和为 4？不存在。最小的奇素数是 3，3+3=6 > 4。 - 所以，这种情况无解。
-
情况二：
p1和p2中至少有一个是偶素数 2。- 由于
p1和p2的地位是相同的（求的是有序对），我们可以假设p1 = 2。 - 等式变为
2 + p2 = p3^2。 - 子情况 2.1：
p2 = 2。2 + 2 = 4 = p3^2，解得p3 = 2。- 我们得到了一个解：
(p1, p2, p3) = (2, 2, 2)。这个解当且仅当N >= 2时成立。
- 子情况 2.2：
p2是一个奇素数。2 (偶) + p2 (奇) = 奇数。- 那么
p3^2必须是奇数，这意味着p3也必须是奇素数。 - 我们要找的就是满足
p2 = p3^2 - 2的素数对(p2, p3)。
- 由于
2. 最终算法
基于以上分析，问题被大大简化了。我们只需要：
- 预处理：使用埃拉托斯特尼筛法，预计算出一个布尔数组
is_prime，标记出1到N范围内的所有质数。 - 计数：
- 初始化
count = 0。 - 处理
(2, 2, 2)：如果N >= 2，那么(2,2,2)是一个有效解，count加 1。 - 处理
(2, p2, p3)和(p2, 2, p3)：- 遍历所有奇素数
p3，从 3 开始。 - 对于每个
p3，计算p2 = p3^2 - 2。 - 剪枝：如果
p3^2 - 2 > N，那么对于更大的p3，p2也一定会超过N，所以可以提前结束循环。这意味着我们只需要遍历p3直到p3 <= sqrt(N+2)。 - 如果计算出的
p2 <= N并且is_prime[p2]为true，那么我们就找到了一个符合条件的素数对(p2, p3)。 - 这对应着两个有序三元组解：
(2, p2, p3)和(p2, 2, p3)。因此count加 2。
- 遍历所有奇素数
- 初始化
这个算法的效率非常高，核心部分只需要一次筛法和一次到 sqrt(N) 的循环。
代码
#include <iostream>
#include <vector>
#include <cmath>
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 n;
cin >> n;
long long count = 0;
if (n >= 2 && is_prime[2]) {
// (2, 2, 2) 的情况
if (2 + 2 == 4 && 4 == 2 * 2) { // 2+2=p3^2 -> p3=2
count++;
}
}
for (long long p3 = 3; p3 <= n; p3 += 2) {
if (!is_prime[p3]) continue;
long long p2 = p3 * p3 - 2;
if (p2 > n) break;
if (is_prime[p2]) {
// (2, p2, p3) 和 (p2, 2, p3)
// p2 不能等于 2，因为 p3 是奇数，p2 也是奇数
count += 2;
}
}
cout << count << endl;
return 0;
}
import java.util.Scanner;
import java.util.Arrays;
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 n = sc.nextInt();
long count = 0;
// (2, 2, 2)
if (n >= 2) {
count++;
}
// (2, p2, p3) and (p2, 2, p3)
for (long p3 = 3; p3 <= n; p3 += 2) {
if (!isPrime[(int)p3]) continue;
long p2_long = p3 * p3 - 2;
if (p2_long > n) break;
int p2 = (int)p2_long;
if (isPrime[p2]) {
count += 2;
}
}
System.out.println(count);
}
}
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
n = int(input())
count = 0
# (2, 2, 2)
if n >= 2:
count = 1
# (2, p2, p3) and (p2, 2, p3)
p3 = 3
while True:
p2 = p3 * p3 - 2
if p2 > n:
break
if p3 <=n and is_prime[p3] and is_prime[p2]:
count += 2
p3 += 2
print(count)
算法及复杂度
- 算法：数论、埃拉托斯特尼筛法
- 时间复杂度：
。
N_max是数据上限，筛法预处理需要。对于每个查询
N，我们遍历p3直到sqrt(N)，因此是。
T是查询次数。 - 空间复杂度：
。需要一个大小为
N_max的布尔数组来存储质数表。
，慢慢来，24届老学长离职两个月，被拷打了30多次了