题解 | #素数对#

题目链接

HIGH10 素数对

题目描述

给定一个正整数 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) 的循环。

代码

cpp
java
python

#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)

算法及复杂度

算法：数论、埃拉托斯特尼筛法
时间复杂度： $\mathcal{O}(N_{max} \log(\log N_{max}) + T \cdot \sqrt{N})$ 。N_max是数据上限，筛法预处理需要 $\mathcal{O}(N_{max} \log(\log N_{max}))$ 。对于每个查询 N，我们遍历 p3 直到 sqrt(N)，因此是 $\mathcal{O}(\sqrt{N})$ 。T 是查询次数。
空间复杂度： $\mathcal{O}(N_{max})$ 。需要一个大小为 N_max 的布尔数组来存储质数表。