一道叫稍微的水题之质数对

问题描述
给一个长度为n的数组，计算有多少对（i，j）满足i<j且a[i]+a[j]是质数
输入
第一行一个数n（1<=n<=2*10^3）
第二行n个数字其中一个数字x满足（1<=x<=10^5）
输出
符合要求的质数个数
输入样例
5
1 2 3 4 5
输出
2
说明
符合条件的有（1，2）和（1，4）

你题目例子错了吧，（1，2）（1，4）（3，4）（2，5）（2，3）


#include<iostream>
#include<cmath>
using namespace std;

bool isPrime(int x) // 判断质数
{
    if(x < 2)
        return false;
    for(int i=2; i<=sqrt(double(x)); i++)
        if(x%i == 0)
            return false;
    return true;
}

int main()
{
    int n, a[2005];
    cin >> n;
    for(int i=0; i<n; i++)
        cin >> a[i];
    int cnt = 0;
    for(int i=0; i<n-1; i++)
        for(int j=i+1; j<n; j++)
            if(isPrime(a[i]+a[j])) // 如果和为质数
                cnt++;
    cout << cnt << endl;
    return 0;
}

感谢大家是发题人发错了数据谢谢大家我给发题人说一下
在此感谢

以下回答由chatgpt基于相关博客总结生成:

优化后的问题描述：给定长度为n的数组A，计算有多少对不同位置的元素能够相加得到一个质数。

解决方案： 1. 首先，我们需要一个判断质数的函数。根据质数的定义，只需判断n是否能够被2~sqrt(n)中任何一个数整除即可。

def is_prime(n):
    if n < 2:
        return False
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            return False
    return True

我们可以用一个哈希表来记录每个数在数组中的出现次数。

from collections import defaultdict

A = [1, 2, 3, 4, 5]
freq = defaultdict(int)
for num in A:
    freq[num] += 1

遍历每一对不同的数，判断它们的和是否为质数，如果是，则累加到结果中。

count = 0
for i in range(n):
    for j in range(i+1, n):
        if is_prime(A[i]+A[j]):
            count += freq[A[i]] * freq[A[j]]

最终的时间复杂度为O(n^2 log n)，可以尝试使用NTT算法优化到O(n log n)。具体步骤：
将两个数组A1和A2分别转成多项式a(x)和b(x)
对a(x)和b(x)做卷积，得到多项式c(x)
将c(x)转成有序对的形式，累加符合要求的对数

n = len(A)
A1 = [freq[i] for i in A]
A2 = [0] * n

def ntt_multiply(a, b):
    # 傅里叶变换前，先对每个数取模，避免中间计算过程中爆long long
    p = 998244353  # 998244353是2^23 * 7 * 17 + 1，可以通过NTT进行乘法计算，且998244353比10^9+7的范围更宽。
    inv2 = pow(2, p-2, p)
    n = len(a)
    A = [a[i] % p for i in range(n)]
    B = [b[i] % p for i in range(n)] + [0] * n
    # 递归结束条件
    if n == 1:
        return [A[0]*B[0]%p]
    else:
        A_even = A[::2]  # 偶数项
        A_odd = A[1::2]  # 奇数项
        B_even = B[::2]
        B_odd = B[1::2]
        C_even = ntt_multiply(A_even, B_even)  # 递归计算偶数项
        C_odd1 = ntt_multiply(A_even, B_odd)   # 由于需要加上i*j项，因此需要先计算(i+j)*(i+j) - i*i - j*j = 2*i*j，此处计算i*j项
        C_odd2 = ntt_multiply(A_odd, B_even)   # 同上
        C_odd = [(C_odd1[i] + C_odd2[i]) * inv2 % p for i in range(n//2)]  # 求递归结果中间项
        C = [0] * n
        for i in range(n//2):
            C[i] = (C_even[i] + C_odd[i] * pow(2, (n//2)*23, p)) % p  # 调整中间项和高位结果
        for i in range(n//2, n):
            C[i] = (C_even[i-(n//2)] + C_odd[i-(n//2)] * pow(2, (n//2)*23, p)) % p
        return C

P = ntt_multiply(A1, A2)
res = 0
for i in range(2, n*2):
    if is_prime(i):
        res += P[i] // 2  # 有序对(i,j)和(j,i)分别计了一次，除以2