牛客 QQ5 素数对
概述
https://www.nowcoder.com/practice/c96d6acc025541ffb79c579688f8d003
解法
那我们首先需要计算出小于等于 n / 2 的所有质数,然后遍历一遍就好了。
LeetCode 有让求小于 n 的所有质数的题:https://iamazing.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;
}
Links: 牛客-qq05-素数对