题目描述

线性筛

时间复杂度

参考文献

C++ 代码

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
const int MX = 1e3 + 5;
int pr[MX];
int v[MX];
int cnt;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    v[1] = 1;
    for(int i = 2 ; i <= 1000 ; i++)
    {
        if(v[i] == 0) pr[++cnt] = i;
        for(int j = 1 ; j <= cnt ; j++)
        {
            if(i * pr[j] > 1000) break;
            v[i * pr[j]] = 1;
            if(i % pr[j] == 0) break;
        }
    }

    int T;
    cin >> T;
    while(T--)
    {
        int n,k;
        cin >> n >> k;
        int ans = 0;
        for(int i = 3 ; i <= cnt ; i++)
        {
            if(pr[i] > n) break;
            int p = pr[i];
            for(int j = 1 ; j < i ; j++)
            {
                if(p == pr[j] + pr[j - 1] + 1) ans++;
            }
        }
        if(ans >= k) cout << "YES" << endl;
        else cout << "NO" << endl;
    }

    return 0;
}