a bit of codechef: Prime Polindromes

Problem Statement:
CodeChef - Prime Polindromes

Summary:
Given an integer \(N\), find the smallest integer \(M \geq N\) such that \(M\) is a palindrome and prime number. Limit: \(1\leq N \leq 10^6\).

Solution:
It is considered an easy problem in CodeChef (Oh my God..) and actually it's not that easy. At first it is tempting to try one by one palindromes \(P\) which is bigger than \(N\) by checking for each whether it is prime. That means for each \(P\), we have to check that \(2,3,4,5,\ldots ,P-1\) do not divide \(P\), this will take \(O(P^2)\) time, and it is bad since the limit for \(N\) is \(10^6\). Even with the fact that we just need to check until \(\sqrt{P}\), this approach will definitely result in a TLE (Time Limit Exceeded). So?

Certainly we have to choose different strategy, a different perspective. What if, we generate all primes we need beforehand? We can construct an array \(A\) consisting of around 1 million elements of 0 or 1, such that if \(i\) is a prime number, \(A[i] = 1\), and 0 otherwise. As such, if we want to check whether \(P\) is a prime, we just need to get the value of \(A[P]\), hence \(O(1)\) for the primality check. This is a dramatic decrease from our initial \(O(P^2)\)!

How can we generate all primes up to 1 million++? This is where this discussion about Sieve of Eratosthenes becomes useful. By running the algorithm to an appropriate value of \(i\), we will generate all primes needed. This will take at most \(N \times (\frac{1}{2}+\frac{1}{3}+\ldots + \frac{1}{N}) = O(N \log{N})\), which means there are around \(10^6 \times \log{10^6} = 6\times 10^6\) computations to generate the primes, quite manageable.

Finally, we just need to observe that a palindrome with even-numbered digit will never be prime, which can be proven quite easily:
Let \(P = a_0a_1...a_{k-1}a_ka_ka_{k-1}...a_1a_0\) be a palindrome with an even total digit. From here we have quite a few ways to proceed, but the easiest would be to take \(\bmod{11}\) of the palindrome, and you'll observe that \(a_i\) will have alternating sign \(\bmod{11}\), which eventually will cancel out and leads to \(P \equiv 0 \bmod{11}\).

Making use of all the information, here is one possible, and rather messy implementation of our solution:

#include <cstdio>
#include <cmath>
//N must have odd digit, if even digit then it's divisible by 11
//N should be less than 10^7
//assume there exist prime of form 1.....1
//generate all primality from 1 to <1020^2
bool prime[1009050];

int pow_10(int n){
   int ret=1;
   for(int i=0;i<n;++i)
      ret*=10;
   return ret;
}

int main(){
   int N;
   scanf("%d",&N);
   for(int i=0;i<=1009050;++i)prime[i]=1;//initialization
   for(int i=2;i<=1020;++i)
      for(int j=2;j<=1009050/i;++j){
         prime[i*j]=0;
      }
   int temp=N,d=0;
   while(temp!=0){ //finding num of digit of N
      ++d;
      temp/=10;
   }

   int s; //starting point of trial and error
   if(d%2==1)s=N/pow_10(d/2);
   else s=pow_10(d/2);
   while(1){ //generating palindromes... messy but correct
      int t=s,e=0;
      while(t!=0){++e;t/=10;}
      int K=s*pow_10(e-1);
      for(int i=1;i<e;++i){
         K+=(s/pow_10(i))%10*pow_10(e-1-i);
      }
      if(prime[K] && K>=N){
         printf("%d\n",K);
         break;
      }
      ++s;
   }
   return 0;
}