## Sunday, June 22, 2014

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