素数对

思路

拿到这道题，我们要找满足 $A + B = C^2$ 的素数三元组 $(A, B, C)$ ，其中 $A, B, C$ 都是素数且都不超过 $N$ 。注意 $(A, B)$ 的顺序不同算不同的三元组。

首先想一个关键的约束：因为 $A \le N$ ， $B \le N$ ，所以 $A + B \le 2N$ ，也就是 $C^2 \le 2N$ ，即 $C \le \sqrt{2N}$ 。当 $N = 5 \times 10^5$ 时， $C$ 最大也就到 $1000$ 左右。这意味着我们需要枚举的 $C$ 的范围非常小！

有了这个观察，算法就很直接了：

筛素数：用埃氏筛预处理出 $[2, N]$ 中所有素数。
枚举 C：对每个素数 $C \le \min(N, \lfloor\sqrt{2N}\rfloor)$ ，计算 $C^2$ 。
枚举 A： $A$ 的范围是 $[\max(2, C^2 - N),\ \min(N, C^2 - 2)]$ ，因为 $B = C^2 - A$ 必须满足 $2 \le B \le N$ 。对范围内的每个素数 $A$ ，检查 $B = C^2 - A$ 是否也是素数，是就计数加一。

由于 $C$ 的范围很小（不超过 $\sqrt{2N}$ ），每个 $C$ 对应的枚举范围也不超过 $C^2 \le 2N$ ，总体计算量是可以接受的。

代码

C++
Java
Python3
JavaScript

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    scanf("%d", &n);
    vector<bool> sieve(n+1, true);
    if(n >= 0) sieve[0] = false;
    if(n >= 1) sieve[1] = false;
    for(int i = 2; (long long)i * i <= n; i++){
        if(sieve[i]){
            for(int j = i*i; j <= n; j += i)
                sieve[j] = false;
        }
    }

    long long ans = 0;
    int clim = (int)sqrt(2.0 * n) + 1;
    for(int c = 2; c <= min(clim, n); c++){
        if(!sieve[c]) continue;
        long long csq = (long long)c * c;
        if(csq < 4) continue;
        int lo = (int)max(2LL, csq - n);
        int hi = (int)min((long long)n, csq - 2);
        if(lo > hi) continue;
        for(int a = lo; a <= hi; a++){
            if(!sieve[a]) continue;
            int b = (int)(csq - a);
            if(sieve[b]) ans++;
        }
    }
    printf("%lld\n", ans);
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        boolean[] sieve = new boolean[n + 1];
        java.util.Arrays.fill(sieve, true);
        if (n >= 0) sieve[0] = false;
        if (n >= 1) sieve[1] = false;
        for (int i = 2; (long) i * i <= n; i++) {
            if (sieve[i]) {
                for (int j = i * i; j <= n; j += i)
                    sieve[j] = false;
            }
        }

        long ans = 0;
        int clim = (int) Math.sqrt(2.0 * n) + 1;
        for (int c = 2; c <= Math.min(clim, n); c++) {
            if (!sieve[c]) continue;
            long csq = (long) c * c;
            if (csq < 4) continue;
            int lo = (int) Math.max(2, csq - n);
            int hi = (int) Math.min(n, csq - 2);
            if (lo > hi) continue;
            for (int a = lo; a <= hi; a++) {
                if (!sieve[a]) continue;
                int b = (int) (csq - a);
                if (sieve[b]) ans++;
            }
        }
        System.out.println(ans);
    }
}

import sys, math

def main():
    n = int(sys.stdin.read())
    if n < 2:
        print(0)
        return
    sieve = [True] * (n + 1)
    sieve[0] = sieve[1] = False
    for i in range(2, int(n**0.5) + 1):
        if sieve[i]:
            for j in range(i*i, n+1, i):
                sieve[j] = False

    ans = 0
    clim = int(math.sqrt(2.0 * n)) + 1
    for c in range(2, min(clim, n) + 1):
        if not sieve[c]:
            continue
        csq = c * c
        if csq < 4:
            continue
        lo = max(2, csq - n)
        hi = min(n, csq - 2)
        if lo > hi:
            continue
        for a in range(lo, hi + 1):
            if not sieve[a]:
                continue
            b = csq - a
            if sieve[b]:
                ans += 1
    print(ans)

main()

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });

rl.on('line', (line) => {
    const n = parseInt(line.trim());
    if (n < 2) {
        console.log(0);
        return;
    }
    const sieve = new Uint8Array(n + 1).fill(1);
    sieve[0] = 0;
    sieve[1] = 0;
    for (let i = 2; i * i <= n; i++) {
        if (sieve[i]) {
            for (let j = i * i; j <= n; j += i)
                sieve[j] = 0;
        }
    }

    let ans = 0;
    const clim = Math.floor(Math.sqrt(2.0 * n)) + 1;
    for (let c = 2; c <= Math.min(clim, n); c++) {
        if (!sieve[c]) continue;
        const csq = c * c;
        if (csq < 4) continue;
        const lo = Math.max(2, csq - n);
        const hi = Math.min(n, csq - 2);
        if (lo > hi) continue;
        for (let a = lo; a <= hi; a++) {
            if (!sieve[a]) continue;
            const b = csq - a;
            if (sieve[b]) ans++;
        }
    }
    console.log(ans);
});

复杂度分析

时间复杂度： $O(N)$ 。筛素数是 $O(N \log\log N)$ 。枚举部分， $C$ 最大到 $\sqrt{2N}$ ，对每个 $C$ 枚举的范围不超过 $C^2$ ，所有素数 $C$ 的 $C^2$ 之和远小于 $N$ ，因此枚举部分总计也是 $O(N)$ 级别。
空间复杂度： $O(N)$ ，用于存储素数筛数组。