Thành phố Hà Nội có một số linh vật được đánh số thứ tự từ A đến B (A,B là hai số nguyên dương A<=B) . Lãnh đọa thành phố quyết định đấu giá những con linh vật có số thứ tự đẹp để lấy tiền ủng hộ đồng bào lũ lụt miền trung . Một số thứ tự được gọi là số đẹp nếu nó thỏa mãn các điều kiện sau : - Là một số nguyên dương T mà A<=T<=B - T là một số nguyen tố - T là một số đối xứng ( đọc T từ trái sang phải giống như đọc T từ phải qua trái ) ví dụ 12321 là một số đối xứng Yêu cầu : cho hai số nguyên dương A và B (A<=B) , hãy tìm số linh vật có số thứ tự đẹp . Input : Tệp văn bàn AUCTION.INP gồm một dòng chứa hai số nguyên dương A và B ( 0<= A<=B<=10^9) Onput. Đưa ra tệp văn bản AUCTION.OUT gồm một số nguyên là số linh vật có số thứ tự đẹp Ví dụ : AUCTION.INP 11111 22222 AUCTION.OUT 23 viết bằng c++ hoặc pascal nếu có thể

- Vì một số đối xứng có dạng: `\overline{ab..ba} (1)` hoặc `\overline{ab..x..ba} (2)`

Trường hợp (1):

+ Ta có thể tìm T = `\overline{ab..}` sau đó đảo T lại và ghép vào sau T

Trường hợp (2):

+ Làm tương tự t.hợp (1) nhưng chèn thêm 1 số x `(0 le x le 9)`

- Sau khi thực hiện xong ta kiểm tra xem T có là số nguyên tố và `a le T le b` là xong

*Lưu ý: bạn có thể sử dụng phép kiểm tra nguyên tố thường (mình dùng miller để giảm đpt) :)

- Code (85 dòng)

#include <iostream>
#include <cmath>
using namespace std;

typedef __int128 IT;
int a, b, res;

// ---------------------------------- // Phép kiểm tra từ đây :)
IT power(IT A, IT N, IT M) {
    IT ret = 1; A = A % M;

    while (N > 0) {
        if (N & 1) ret = ret * A % M;
        N >>= 1;
        A = A * A % M;
    }

    return ret;
}

bool check(IT A, IT s, IT d, IT N) {
    if (N == A) return true;
    IT p = power(A, d, N);
    if (p == 1) return true;

    for(; s > 0; s--) {
        if (p == N - 1) return true;
        p = p * p % N;
    }

    return false;
}

bool prime(IT x) {
    if (x <= 1) return false;
    if (x % 2 == 0) return x == 2;
    if (x % 3 == 0) return x == 3;

    IT d = x - 1, s = 0;
    while ((d & 1) == 0) {
        s++;
        d >>= 1;
    }

    for(IT i: {2, 7, 61})
        if (!check(i, s, d, x)) return false;

    return true;
}
// ------------------------------//

int rev(int x) {
    int r = 0;
    while (x) r *= 10, r += x % 10, x /= 10;
    return r;
}

int count(int x) {
    return log10(x) + 1;
}

bool check(int x) {
    if (a <= x && x <= b) {
        if (prime(x)) {
        //    cout << x << "\n";
            return 1;
        }
    }
    return 0;
}

void solve(int x) {
    int tmp = rev(x), c = pow(10, count(x));
    res += check(x * c + tmp);
    for (int i = 0; i < 10; ++i) res += check(x * c * 10 + i * c + tmp);
}

void gene() {
    for (int i = pow(10, count(b) / 2); i > 0; --i) solve(i);
}

int main() {
    cin >> a >> b;
    for (int i: {2, 3, 5, 7}) res += check(i);
    gene();
    cout << res;
}