题解：P12157 [蓝桥杯 2025 省 Java B] 魔法科考试

· · 题解

传送门
时限很大，所以埃氏筛+桶就能过这题。 也就是，先把素数筛出来，再枚举一遍，看一看是否符合题目要求：质数，和小于 n+m，无重复（千万要注意！）。 

#include<bits/stdc++.h>
using namespace std;
int p[41000],a[40010],b[40010],t[40010];
void shai(){//埃氏筛
    p[0] = p[1] = 1;
    for(int i = 2;i*i<=40000;i++)if(!p[i])for(int j = 2;i*j<=40000;j++)p[i*j] = 1;
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cout.tie(0);
    shai();
    int n,m,cnt = 0;
    cin>>n>>m;
    for(int i = 1;i<=n;i++)cin>>a[i];
    for(int i = 1;i<=m;i++)cin>>b[i];
    for(int i = 1;i<=n;i++)for(int j = 1;j<=m;j++)if(a[i]+b[j]<=n+m&&!p[a[i]+b[j]]&&!t[a[i]+b[j]])cnt++,t[a[i]+b[j]] = 1;//爆搜
    cout<<cnt;
    return 0;
}

时限三秒是种什么感受？测试点跑出 1.12 秒都能过！