题解 | #素数对#

题目链接

素数对

题目描述

请你找出满足 $A + B = C^2$ ，且 $A, B, C$ 均为小于等于 $N$ 的素数的三元组 $(A, B, C)$ 的数量。

解题思路

1. 数学性质分析

我们来分析方程 $A + B = C^2$ ，其中 $A, B, C$ 都是小于等于 $N$ 的素数。核心在于利用素数的奇偶性。

情况一：C = 2

如果 $C=2$ （唯一的偶素数），那么 $C^2 = 4$ 。方程变为 $A+B=4$ 。

要使两个素数的和为 4，唯一解是 $A=2, B=2$ 。

因此，三元组 (2, 2, 2) 是一个潜在的解。它成立的条件是所有元素都不超过 $N$ ，即 $2 \le N$ 。
情况二：C > 2

如果 $C$ 是一个大于 2 的素数，那么 $C$ 必然是奇数。
- 奇数的平方（ $C^2$ ）也是奇数。
- 方程 A + B = 奇数 成立的唯一可能是，A 和 B 中一个是偶数，另一个是奇数。
- 由于 A 和 B 都是素数，唯一的偶素数是 2。因此，A 和 B 中必须有一个是 2。
- 不妨设 $A=2$ ，方程变为 $2 + B = C^2$ ，即 $B = C^2 - 2$ 。

2. 问题转化

基于以上分析，问题被转化为寻找满足特定条件的素数组合：

检查 (2, 2, 2) 是否是一个有效解。
寻找所有满足以下条件的素数 C：
- $C$ 是一个大于 2 的素数且 $C \le N$ 。
- $B = C^2 - 2$ 也是一个素数且 $B \le N$ 。

对于每一个找到的这样的 C，由于 $C > 2$ 导致 $B = C^2 - 2 > 2$ ，所以 $A \ne B$ 。这对应着两个不同的有序三元组：(2, B, C) 和 (B, 2, C)。

3. 算法设计

我们可以通过枚举素数 C 来寻找解。

约束简化：从 $B = C^2 - 2 \le N$ 可以推导出 $C^2 \le N+2$ ，即 $C \le \sqrt{N+2}$ 。这是一个比 $C \le N$ 更强的约束，可以大大缩小我们枚举 C 的范围。
预处理：使用埃拉托斯特尼筛法预计算出 $N$ 以内的所有素数，存入一个布尔数组 is_prime 中，方便快速查询。
计数：

a. 初始化 count = 0。

b. 处理 C=2 的情况：如果 $N \ge 2$ ，则 (2, 2, 2) 是一个有效解，count 置为 1。

c. 处理 C>2 的情况：遍历所有奇数 $C$ 从 3 到 $\sqrt{N+2}$ 。
- 如果 $C$ 是素数（通过查询 is_prime[C]），则计算 $B = C^2 - 2$ 。
- 检查 $B$ 是否为素数（is_prime[B]）。
- 如果 $B$ 也是素数，说明我们找到了一个有效的 (B, C) 对，这对应两个解，count 增加 2。
d. 最终的 count 就是答案。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

vector<bool> sieve(int n) {
    vector<bool> is_prime(n + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (int p = 2; p * p <= n; p++) {
        if (is_prime[p]) {
            for (int i = p * p; i <= n; i += p)
                is_prime[i] = false;
        }
    }
    return is_prime;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    if (n < 2) {
        cout << 0 << endl;
        return 0;
    }

    vector<bool> is_prime = sieve(n);
    long long count = 0;

    // Case 1: C = 2
    if (n >= 2) {
        // A=2, B=2, C=2 => 2+2=2*2. Valid.
        count = 1;
    }

    // Case 2: C > 2
    int limit = sqrt(n + 2);
    for (int c = 3; c <= limit; c += 2) {
        if (is_prime[c]) {
            long long b = (long long)c * c - 2;
            if (b <= n && is_prime[b]) {
                count += 2;
            }
        }
    }

    cout << count << endl;

    return 0;
}

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static boolean[] sieve(int n) {
        boolean[] isPrime = new boolean[n + 1];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        for (int p = 2; p * p <= n; p++) {
            if (isPrime[p]) {
                for (int i = p * p; i <= n; i += p) {
                    isPrime[i] = false;
                }
            }
        }
        return isPrime;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        if (n < 2) {
            System.out.println(0);
            return;
        }

        boolean[] isPrime = sieve(n);
        long count = 0;

        // Case 1: C = 2
        if (n >= 2) {
            // A=2, B=2, C=2 => 2+2=2*2. Valid.
            count = 1;
        }

        // Case 2: C > 2
        int limit = (int) Math.sqrt(n + 2);
        for (int c = 3; c <= limit; c += 2) {
            if (isPrime[c]) {
                long b = (long)c * c - 2;
                if (b <= n && isPrime[(int)b]) {
                    count += 2;
                }
            }
        }

        System.out.println(count);
    }
}

import sys
import math

def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    for p in range(2, int(n**0.5) + 1):
        if is_prime[p]:
            for i in range(p * p, n + 1, p):
                is_prime[i] = False
    return is_prime

def solve():
    try:
        n_str = sys.stdin.readline()
        if not n_str: return
        n = int(n_str)
    except (IOError, ValueError):
        return

    if n < 2:
        print(0)
        return

    is_prime = sieve(n)
    count = 0

    # Case 1: C = 2
    if n >= 2:
        # A=2, B=2, C=2 => 2+2 = 2*2. Valid.
        count = 1
    
    # Case 2: C > 2
    limit = int(math.sqrt(n + 2))
    for c in range(3, limit + 1, 2):
        if is_prime[c]:
            b = c * c - 2
            if b <= n and is_prime[b]:
                count += 2
        
    print(count)

solve()

算法及复杂度

算法：数论 / 埃拉托斯特尼筛法
时间复杂度： $O(N \log \log N)$ 。
- 算法的瓶颈在于埃氏筛预处理素数，其时间复杂度为 $O(N \log \log N)$ 。
- 后续遍历 C 的循环次数远小于 $N$ （约为 $\sqrt{N}$ ），因此其时间复杂度被筛法覆盖。
空间复杂度： $O(N)$ 。
- 我们需要一个大小为 $N+1$ 的布尔数组来存储素数信息。