Mirror Primes
National Olympiad — National round (2013 season)
Submission name: mirror.cpp
Problem summary
Count the integers between M and N, inclusive in either input order, that are prime and remain prime when their decimal digits are reversed. Palindromic primes count too.
Input
Two natural numbers M and N.
Output
The count of mirror primes in the inclusive interval.
Constraints
1 < M,N ≤ 100,000.
Worked example
An independently prepared example for this explanation.
Input
10 25
Output
3
Solution analysis
- Build a sieve of primes through 100000. All relevant reversed values fit this bound: numbers below 100000 have at most five digits, while 100000 reverses to 1.
- Visit the interval from min(M,N) to max(M,N). Reverse each candidate numerically and count it if both primality flags are true.
- Between 10 and 25, the successful numbers are 11,13,17, whose reversals are 11,31,71. Hence the answer is 3.
Why it works
The sieve marks exactly the primes. Each interval integer is tested once against the two required prime conditions, so exactly the mirror primes contribute one to the answer. Reordering endpoints does not alter the inclusive set.
Watch out. Input endpoints may be reversed. Palindromes such as 101 are allowed. The number 1 is not prime.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int m, n;
cin >> m >> n;
const int limit = 100000;
vector<bool> prime(limit + 1, true);
prime[0] = false;
prime[1] = false;
for (int p = 2; p * p <= limit; p++) {
if (prime[p]) {
// Smaller multiples were already marked by smaller prime factors.
for (int multiple = p * p; multiple <= limit; multiple += p) {
prime[multiple] = false;
}
}
}
int answer = 0;
for (int value = min(m, n); value <= max(m, n); value++) {
int remaining = value;
int reversed = 0;
while (remaining > 0) {
reversed = reversed * 10 + remaining % 10;
remaining /= 10;
}
if (prime[value] && prime[reversed]) {
answer++;
}
}
cout << answer << '\n';
}