题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
质数筛一遍打表,直接枚举2–n之间的所有质数,然后循环所有质数就行,只要存在就直接break,题目要求我们找到不同的质数等于两个相邻的质数 + 1
C++ 代码
#include "bits/stdc++.h"
#define int long long
using namespace std;
const int N = 1010;
int st[N];
int primes[N];
int cnt;
void get_primes(int n) {
memset(st, false, sizeof st);
cnt = 0;
for(int i = 2; i <= n; i++) {
if(!st[i]) primes[cnt++] = i;
for(int j = 0; primes[j] * i <= n; j++) {
st[primes[j] * i] = true;
if(i % primes[j] == 0) break;
}
}
}
void solve() {
get_primes(N);
int n, k;
cin >> n >> k;
int res = 0;
for (int i = 2; i <= n; i++) {
if (st[i]) continue;
for (int j = 1; j < cnt; j++) {
if (primes[j - 1] + primes[j] + 1 == i) {
res++;
break;
}
}
}
cout << (res >= k ? "YES" : "NO") << '\n';
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T; cin >> T;
while (T --) {
solve();
}
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla