题目
D - Five, Five Everywhere
寻找n个素数，使得这n个素数中任意5个数之和都是合数。
思路
- 如果一个数除5余1，那么5个这样的数之和一定能被5整除；
- 筛出范围内所有满足上述条件，且为素数的数即可。
总结
- 如何想到除五余一这一点呢？
- 首先应思考如何构造合数，想到如果是5个数之和，那么就让这些数的和时满足被5整除最好，这样在选择不同的数时，能够利用个数确定保持某些不变性。
代码
点击查看代码
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
using LL = long long;
const int N = 55555;
int primes[N], cnt;
bool st[N];
vector<int> ans;
void get_primes(int n)
{
for (int i = 2; i <= n; i ++)
{
if (st[i] == false)
{
primes[cnt ++] = i;
if (i % 5 == 1)
ans.push_back(i);
}
for (int j = 0; primes[j] <= n / i; j ++)
{
st[primes[j] * i] = true;
if (i % primes[j] == 0)
break;
}
}
}
void solv()
{
int n;
cin >> n;
get_primes(N - 1);
// cout << ans.size() << endl;
for (int i = 1; i <= n; i ++)
cout << ans[i] << " ";
cout << '\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T = 1;
// cin >> T;
while (T--)
solv();
return 0;
}