* Thuật toán: Vì bài này k<=7 nên ta có thể sử dụng thuật toán vét cạn.

* Cách thức: Ta chạy 1 vòng for từ 1 -> 9, 1 vòng for chạy từ 0 -> 9 (vì 0 không được ở đầu số nên chạy từ 1). Ta phải kiểm tra điều kiện a ne b, vì đề yêu cầu số thứ k+1 phải khác các số còn lại. Ta cho k số a vào bên phải số n (a chạy từ 1->9), tiếp đến đặt số b ở vị trí k+1 (b ne a), rồi đặt k số a còn lại vào bên trả số n để tạo thành số theo yêu cầu đề bài. Sau khi đã tạo ra số n ta kiểm tra xem n có phải số nguyên tố hay không, nếu đúng thì số n thoã mãn đề bài, ta tăng biến res lên 1.

* Lưu ý: Độ phức tạp thuật toán tổng quát là O(9^2 + sqrt(10^(2n+1))), thế nên với n=7 thì độ phức tạp là rất lớn O(9^2 + sqrt(10^15)) Vì cậy ta đặt điều kiện nếu k=7 thì kết quả sẽ là 7 khong cần tính toán nữa để tránh bị tle.

#include
#define ll long long

using namespace std;

bool check(ll n)
{
    if (n < 2)
        return false;
    for (ll i = 2; i * i <= n; i++)
    {
        if (n % i == 0)
            return false;
    }
    return true;
}

int main()
{
    ll k, n = 0, res = 0;
    cin >> k;
    if(k==7) return cout<<7 , 0;
    for (ll i = 1; i <= 9; i++)
    {
        for (ll j = 0; j <= 9; j++)
        {
            if (i != j)
            {
                for (ll m = 1; m <= k; m++)
                {
                    n = n * 10 + i;
                }
                n = n * 10 + j;
                for (ll m = 1; m <= k; m++)
                {
                    n = n * 10 + i;
                }
                if (check(n))
                    res++;
            }
            n = 0;
        }
    }
    cout << res;
}

Với vấn đề này mình sẽ vét cạn từng trường hợp số có 2k+1 và kiểm tra tính nguyên tố của từng trường hợp, vì số chẵn không phải số nguyên tố nên mình sẽ bỏ qua trường hợp các chữ số bên ngoài là số chẵn, việc này sẽ giúp làm giảm độ phức tạp khi tính toán.

Ngoài ra, mình cũng tối ưu hàm kiểm tra nguyên tố bằng cách kiểm tra bội của 2 và 3 trước, điều này giúp việc kiểm tra nguyên tố diễn ra mà không bị TLE.

$$\\$$

$$\color{#1fdb91}{\texttt{C}}\color{#0aaec9}{\texttt{+}}\color{#e9418e}{\texttt{+}}$$

#include

#define ll long long

using namespace std;

ll k, res;

bool isPrime(ll x) {
    if (x == 2 || x == 3) return true;
    if (x < 2 || x % 2 == 0 || x % 3 == 0) return false;
    for (ll i=5; i*i<=x; i+=6) {
        if (x % i == 0 || x % (i+2) == 0) return false;
    }
    return true;
}

ll createNum(ll mid, ll other) {
    string res;
    for (ll i=1; i<=k; ++i) res += (char)other+'0';
    res += (char)mid+'0';
    for (ll i=1; i<=k; ++i) res += (char)other+'0';
    return stoll(res);
}

void solve(ll mid, ll other) {
    if (mid > 9 || other > 9) return;
    if (isPrime(createNum(mid, other))) ++ res;
    solve(mid, other+2);
}

int main() {
    
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> k;
    for (ll mid=0; mid<=9; ++mid) solve(mid, 1);
    
    cout << res;
    
}

// Author : Daoanhviet96
// Language : C++

\begin{array}{c|c|c}\color{#ffd710}{\texttt{\{}} \color{#8655d6}{\texttt{\{}}\ \ \color{#8cdcda}{\text{Daoanhviet96}}\ \ \color{#8655d6}{\texttt{\}}} \color{#ffd710}{\texttt{\}}}\end{array}