Gọi hàm ~isGood(x)~ là hàm xác định phần tử ~a_i~ thỏa mãn đề bài, ~isGood(x) = 1~ khi ~0 < a_i \leq X~ và ~a_i~ là số nguyên tố, ngược lại ~isGood(x) = 0~.

Gọi ~p_i~ là số các số thỏa mãn ~isGood(x) = 0~ từ ~1~ đến ~i~.

Gọi ~cnt~ là số lượng số thỏa mãn ~isGood(x) = 1~.

Nhận xét: Ta cần nhét hết tất cả các số có ~isGood(x) = 1~ nằm cạnh nhau, giả sử ta đang xét ở phần tử thứ ~i~ thì để nhét đủ ta cần các số trong đoạn ~[i-cnt+1,i]~ thỏa mãn ~isGood(x) = 1~.

Vì các số thỏa mãn yêu cầu đề bài có thể nằm bất cứ đâu nhưng cách tối ưu để xếp cạnh nhau là đưa các số ~isGood(x) = 1~ ngoài đoạn ~[i-cnt+1,i]~ về vị trí các số ~isGood(x) = 0~ mà nằm cạnh các số ~isGood(x) = 1~ trong đoạn ~[i-cnt+1,i]~. Vậy đáp án bài toán chính là ~min(p_i-p_{i-cnt+1})~ với ~i-cnt+1 < i \leq n~.

Code mẫu

#include <iostream>
#include <stdio.h>
#include <vector>
#include <cmath>
#include <math.h>
#include <map>
#include <algorithm>
#include <set>
#include <bitset>
#include <queue>
#include <cstring>
#include <stack>
#include <iomanip>
#include <assert.h>

#define _(x) (1LL<<(x))
#define BIT(x,pos) (((x)>>(pos)) & 1LL)
#define turn_all(x) (_(x)-1LL)
#define bitCnt(x) __builtin_popcountll(x)

#define name "test"
#define nameTask ""
#define fastIO ios::sync_with_stdio(false); cin.tie(0);

using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<int,ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;

const int N = 1E6;
const int INF = 1E9;

int notPrime[N+9];
int n, x;
bool f[N+9];
int cntPrime = 0;

void sieve()
{
    f[1] = f[0] = 1;
    for (int i = 2;i <= trunc(sqrt(N)); ++i)
        if (f[i] == 0)
            for (int j = i + i;j <= N; j += i)
                f[j] = 1;
}

int main()
{
    fastIO

    cin>>n>>x;

    sieve();
    for (int i = 1;i <= n; ++i)
    {
        int T;
        cin>>T;
        cntPrime += (0 < T && T <= x && f[T] == 0);
        notPrime[i] = notPrime[i-1] + !(0 < T && T <= x && f[T] == 0);
    }

    int ans = INF;
    for (int i = cntPrime;i <= n; ++i)
    {
        int j = i - cntPrime + 1;
        int cnt0 = notPrime[i] - notPrime[j-1];
        ans = min(ans, cnt0);
    }

    cout<<ans;
}