Một số được gọi là số nguyên tố cân bằng nếu nó là số nguyên tố có 2k + 1 chữ số trong đó có 2k chữ số giống nhau và có đúng một chữ số ở vị trí chính giữa (tức vị trí thứ k+1 từ trái sang phải )là khác với các chữ số còn lại chẳng hạn số 7778777 là số nguyên tố cân bằng .

yêu cầu nhập từ bàn phím một số nguyên dương k

hãy tính và in ra màn hình số lượng các số nguyên tố cân bằng có 2k + 1 chữ số

input

3

output

7

Viết code bằng C++

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