题解 | #QQ5 素数对#(哈希表+模拟)

解题思路

1.枚举[1:1000]区间的素数,统计素数对时需要去重(定义第一个数小于等于第二个数即可);

代码

#include <bits/stdc++.h>

using namespace std;

bool check(int t){ //校验i是否为质数　i > 1
    if(t < 4) return true;
    for(int i = 2; i * i <= t; i++){
        if(t % i == 0) return false;
    }
    return true;
}

int main(){
    int x;
    cin >> x;
    unordered_set<int> f; //保存[1:1000]区间范围的质数
    int cnt = 0;
    for(int i = 2; i < 1000; i++){
        if(check(i)) f.insert(i);
    }
    for(auto& val : f){
        if(f.count(x - val) && 2 * val <= x) cnt++; //定义第一个数小于等于第二个数 去重
    }
    cout << cnt;
    return 0;
}