https://www.acwing.com/problem/content/3795
题目要求一个数是质数
且这个数能被两个相邻质数+1之和得到
并且满足这样的条件 还要大于k次
主要难点就是读题意
读懂题意后可以直接使用线性筛把质数预处理一遍
质数都存在st和primes中
预处理质数后直接遍历st找到一个质数
再遍历primes找到相邻质数判断 再res++即可
T<=30 n,k<=1000,不会超时
#include<cstring>
#include<iostream>
using namespace std;
const int N = 10010;
int t;
int primes[N],cnt;
bool st[N];
int res;
void get_primes(int n)
{
for(int i=2;i<=n;i++)//从2开始枚举所有数
{
//找到素数,就加入primes中
if(st[i]==false)primes[cnt++]=i;
//从小到大枚举所有质数
for(int j = 0; primes[j] <= n / i;j ++ )//也可以primes[j]*i<=n,表示枚举所有以primes[j]为最小质因子的数
{
st[primes[j]*i]=true;//每次把质数和i的乘积筛掉
if(i % primes[j]==0)break; //primes[j]一定是i的最小质因子
//因为primes[j]是从小到大枚举的,那么一旦primes[j]可以整除i,它就是最小的质因数
//因此primes[j]一定是primes[j]*i最小质因子
}
//核心:每一个数,不管是合数还是质数,都只会被它的最小质因子筛唯一一次,所以是线性的
}
}
int main()
{
cin >> t;
get_primes(N-1);
while(t--)
{
int n,k;
res=0;
cin >> n >> k;
for(int i=2;i<=n;i++)
{
if(!st[i])//i是质数
{
for(int j=0;j<cnt-1;j++)
{
if(primes[j]+primes[j+1]+1==i)
{
res++;
break;
}
}
}
}
if(res>=k)cout << "YES" << endl;
else cout << "NO" << endl;
}
}