牛客 QQ5 素数对

概述

https://www.nowcoder.com/practice/c96d6acc025541ffb79c579688f8d003

解法

那我们首先需要计算出小于等于 n / 2 的所有质数，然后遍历一遍就好了。

LeetCode 有让求小于 n 的所有质数的题：https://justsong.cn/page/leetcode-204-count-primes

#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<bool> nums(n + 1, true);
    nums[1] = false;
    for (int i = 2; i <= sqrt(n); i ++) {
        if (nums[i]) {
            for (int j = i * i; j <= n; j += i) {
                nums[j] = false;
            }
        }
    }
    int count = 0;
    for (int i = 1; i <= n / 2; i ++) {
        if (nums[i] && nums[n-i]) count ++;
    }
    cout << count;
}