题解 | #素数对#

题目链接

素数三元组

题目描述

给定一个正整数 $N$ ，我们称有序三元组 $(p_1, p_2, p_3)$ 为素数三元组，当且仅当满足下述两条：

$p_1, p_2, p_3$ 均为素数；
$p_1 + p_2 = p_3^2$ 。

请你计算，不超过 $N$ 的素数中，一共有多少个不同的素数三元组 $(p_1, p_2, p_3)$ 满足上式。

解题思路

这是一个需要结合数论知识和高效算法来解决的计数问题。直接暴力枚举所有不超过 $N$ 的三个素数组合会非常慢，我们需要找到更优化的方法。

利用奇偶性进行分析

一个关键的突破口在于分析素数的奇偶性。我们知道，唯一的偶素数是 $2$ ，其他所有素数都是奇数。
- 情况一： $p_1$ 和 $p_2$ 都是奇素数。此时它们的和 $p_1 + p_2$ 是一个偶数。如果 $p_3^2 = p_1 + p_2$ ，那么 $p_3^2$ 也必须是偶数，这意味着 $p_3$ 必须是偶数。唯一的偶素数是 $2$ ，所以 $p_3=2$ 。方程变为 $p_1 + p_2 = 2^2 = 4$ 。不存在两个奇素数的和为 $4$ （ $3+1=4$ 但 $1$ 不是素数），因此这种情况不成立。
- 情况二： $p_1$ 和 $p_2$ 中至少有一个是 $2$ 。
通过这个分析，我们得出结论：任何满足条件的素数三元组中， $p_1$ 和 $p_2$ 之中必定有一个是 $2$ 。
简化问题

由于三元组是有序的，我们需要考虑 $p_1 = 2$ 和 $p_2 = 2$ 两种情况。这两种情况都将原方程 $p_1 + p_2 = p_3^2$ 简化为了 $2 + p_{\text{other}} = p_3^2$ 的形式，其中 $p_{\text{other}}$ 是另一个素数。

我们可以改写方程为 $p_{\text{other}} = p_3^2 - 2$ 。
算法设计

基于以上分析，我们可以设计出高效的算法：
- 预处理：首先，使用埃拉托斯特尼筛法（埃氏筛）预处理出一个布尔数组 $is\_prime$ ，标记出从 $1$ 到 $N$ 范围内的所有素数。
- 遍历：遍历所有不超过 $N$ 的素数 $p_3$ 。
- 计算和检验：对于每一个素数 $p_3$ ，我们计算出 $p_{\text{other}} = p_3^2 - 2$ 的值。
- 然后，我们检查这个计算出的 $p_{\text{other}}$ 是否也是一个不超过 $N$ 的素数。这可以通过查询预处理好的 $is\_prime$ 数组在 $\mathcal{O}(1)$ 时间内完成。
- 计数：
  - 如果 $p_{\text{other}}$ 是一个合法的素数（即 $p_{\text{other}} \le N$ 且为素数），我们就找到了满足条件的素数对 $(p_{\text{other}}, p_3)$ 。
  - 如果 $p_{\text{other}} = 2$ ，这对应着三元组 $(2, 2, p_3)$ 。这种情况只会计数一次。
  - 如果 $p_{\text{other}} \neq 2$ ，这对应着两个有序三元组： $(2, p_{\text{other}}, p_3)$ 和 $(p_{\text{other}}, 2, p_3)$ 。因此计数需要加 $2$ 。
- 优化：在遍历 $p_3$ 的过程中，一旦发现 $p_3^2 - 2 > N$ ，就可以提前终止循环，因为后续的 $p_3$ 只会使这个差值变得更大。

代码

c++
java
python

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int N;
    cin >> 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;
            }
        }
    }

    long long count = 0;
    for (int p3 = 2; p3 <= N; ++p3) {
        if (is_prime[p3]) {
            long long p_other = (long long)p3 * p3 - 2;
            if (p_other > N) {
                break;
            }
            if (p_other > 0 && is_prime[p_other]) {
                if (p_other == 2) {
                    count++;
                } else {
                    count += 2;
                }
            }
        }
    }

    cout << count << endl;
    return 0;
}

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

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

        boolean[] is_prime = new boolean[N + 1];
        Arrays.fill(is_prime, 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;
                }
            }
        }

        long count = 0;
        for (int p3 = 2; p3 <= N; p3++) {
            if (is_prime[p3]) {
                long p_other = (long)p3 * p3 - 2;
                if (p_other > N) {
                    break;
                }
                if (p_other > 0 && is_prime[(int)p_other]) {
                    if (p_other == 2) {
                        count++;
                    } else {
                        count += 2;
                    }
                }
            }
        }
        System.out.println(count);
    }
}

def main():
    N = int(input())
    
    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
    
    count = 0
    for p3 in range(2, N + 1):
        if is_prime[p3]:
            p_other = p3 * p3 - 2
            if p_other > N:
                break
            
            if p_other > 0 and is_prime[p_other]:
                if p_other == 2:
                    count += 1
                else:
                    count += 2
                    
    print(count)

if __name__ == "__main__":
    main()

算法及复杂度

算法：数论（质数筛法、奇偶性分析）
时间复杂度：预处理阶段使用埃氏筛法，时间复杂度为 $\mathcal{O}(N \cdot \log \log N)$ 。后续遍历所有不超过 $N$ 的素数来寻找三元组，这部分操作的次数远小于 $N$ ，可以近似看作 $\mathcal{O}(N)$ 。因此，总时间复杂度由筛法主导，为 $\mathcal{O}(N \cdot \log \log N)$ 。
空间复杂度：需要一个布尔数组来存储每个数是否为质数，空间复杂度为 $\mathcal{O}(N)$ 。