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

deng2013 · 2025-04-20 13:02:56 · 题解

思路

这道题的难点就是我们会不会用埃式筛判断 s 是否是质数。

埃式筛

vector<bool>  init(int N){
    vector<bool> isPrime(N+5,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;
}

已经知道那些数是质数了，下面的就简单了，遍历每个 a_i 和 b_j 判断 s 是否是质数和满不满足 s \le n+m，最后用 set 记录并去重，输出 set 的长度就行了。

代码

#include<bits/stdc++.h>
using namespace std;
vector<bool>  init(int N){//埃式筛
    vector<bool> isPrime(N+5,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;
}
int main(){
    int n,m;
    cin>>n>>m;
    vector<int> a(n),b(m);
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<m;i++) cin>>b[i];
    vector<bool> isprime=init(n+m);
    set<int> st;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(a[i]+b[j]<=n+m&&isprime[a[i]+b[j]]) st.insert(a[i]+b[j]);//判断。
        }
    }
    cout<<st.size();//st的长度。
    return 0;
}