"Mirror prime" numbers#22

"Mirror prime" numbers (Editorial)

Solution

General Idea: A number is called a "mirror prime" if: 1. The number itself is prime. 2. The number obtained after reversing its digits is also prime.

Because the constraints are small ( $1 \leq a \leq b \leq 10000$ 1 \le a \le b \le 10000), we can: - Precompute all primes up to 10000 using the sieve of Eratosthenes. - For each number in the interval $[a, b]$ , reverse its digits and check if both the original and reversed numbers are prime.

Reversing digits is done easily using string manipulation.

The overall time complexity is $O (N)$ after sieve construction.

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int N = 10000;
    vector<int> vis(N+1, 0), prime(N+1, 0);

    // Sieve of Eratosthenes
    for (int i = 2; i <= N; i++) {
        if (vis[i]) continue;
        prime[i] = 1;
        for (int j = i; j <= N; j += i) {
            vis[j] = 1;
        }
    }

    int a, b;
    cin >> a >> b;

    int cnt = 0;
    for (int i = a; i <= b; i++) {
        if (prime[i]) {
            string s = to_string(i);
            reverse(s.begin(), s.end());
            int rev = stoi(s);
            if (prime[rev]) cnt++;
        }
    }
    cout << cnt;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();
    return 0;
}