一、题目
1、原题链接
3792. 质数问题
2、题目描述
给定两个整数 n 和 k，请你判断在 [2,n] 的范围内是否存在不少于 k 个质数，满足可以表示为两个相邻质数与 1 的和。
例如，19 满足条件，因为 19=7+11+1。
输入格式
第一行包含整数 T，表示共有 T 组测试数据。
每组数据占一行，包含两个整数 n 和 k。
输出格式
每组数据输出占一行，如果存在不少于 k 个质数满足条件则输出 YES，否则输出 NO。
数据范围
1≤T≤30,2≤n≤1000,0≤k≤1000
输入样例：
5
27 2
45 7
2 0
15 1
17 1
输出样例：
YES
NO
YES
YES
YES
二、解题报告
1、思路分析
我的思路
（1）利用埃氏筛法将1~n中的质数筛选出来。
（2）然后来判断每两个相邻的质数之和加1，组成的数是否出现在被筛选出的质数中。可以利用哈希表进行该步操作。
y总思路
思路来源：y总讲解视频
y总yyds
（1）先利用线性筛法将1~1000中的质数筛出来。
（2）按题目要求，枚举指定范围内的质数，判断是否可以满足题目条件。
2、时间复杂度
埃氏筛法时间复杂度为O(loglogn)，线性筛法时间复杂度为O(n)
3、代码详解
我的思路代码
#include <iostream>
#include <cstring>
#include <unordered_set>
using namespace std;
const int N=1010;
int T,n,k;
int primes[N],cnt;
unordered_set<int> s;
bool st[N];
int ans;
//埃氏筛法筛质数
void getPrimes(int n){
for(int i=2;i<=n;i++){
if(!st[i]){
primes[cnt++]=i;
s.insert(i);
for(int j=i+i;j<=n;j+=i){
st[j]=true;
}
}
}
}
int main(){
cin>>T;
while(T--){
cin>>n>>k;
memset(primes,0,sizeof primes);
memset(st,0,sizeof st);
s.clear();
ans=0;
cnt=0;
getPrimes(n);
for(int i=0;i<cnt-1;i++){
//在哈希表中进行查找，判断这两个相邻的质数是否满足条件
if(s.count(primes[i]+primes[i+1]+1)) ans++;
}
if(ans>=k) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}
y总思路代码
#include <iostream>
using namespace std;
const int N=1010;
int primes[N];
bool st[N];
int cnt;
int T,n,k;
//线性筛法
void getPrimes(int n){
for(int i=2;i<=n;i++){
if(!st[i]) primes[cnt++]=i;
for(int j=0;primes[j]<=n/i;j++){
st[i*primes[j]]=true;
if(i%primes[j]==0) break;
}
}
}
int main(){
cin>>T;
getPrimes(1000); //将1~1000的质数筛出来
while(T--){
cin>>n>>k;
int ans=0;
//枚举每个质数，判断是否满足条件
for(int i=2;i<=n;i++){
if(!st[i]){
for(int j=1;j<cnt;j++){
if(i==primes[j]+primes[j-1]+1){
ans++;
break;
}
}
}
}
if(ans>=k) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}
三、知识风暴
筛质数
埃氏筛法
基本思想：枚举每个数，将每个质数的倍数删掉，得到的没有被删掉的数即为质数。
线性筛法
将朴素版筛法优化到了线性时间复杂度
