#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

#define ll long long

bool check(ll n)
{
    if (n < 2)
        return false;
    if (n < 4)
        return true;
    if (n % 2 == 0 || n % 3 == 0)
        return false;
    for (ll i = 5; i <= sqrt(n); i += 6)
    {
        if (n % i == 0 || n % (i + 2) == 0)
        {
            return false;
        }
    }
    return true;
}

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

    ll n;
    cin >> n;
    ll res = 0;
    for (ll i = 1; i <= 9; i++)
    {
        for (ll j = 0; j <= 9; j++)
        {
            ll t = 0;
            for (ll k = 0; k < n; k++)
            {
                t = t * 10 + i;
            }
            t = t * 10 + j;
            for (ll k = 0; k < n; k++)
            {
                t = t * 10 + i;
            }
            if (check(t)) res++;
        }
    }
    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 <bits/stdc++.h>

#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}