PRIME_PALIN.cpp

#include <iostream>
using namespace std;
 
/*
///////////////////////////////////////////////////////////////////////////////////
//
// This commented out code was used to generate the array of prime palindromes :D
//
// But there is a glitch , I am using fermat's primality test to check if a number is
// prime or not. Fermat's primality test is a probabilistic test, meaning it can go wrong
// and declare composite numbers to be prime. Though it always declares prime numbers 
// to be primes. So we need to double check the list of prime_palindromes generated here
// to see if there are any composite numbers. The best way is to run the Fermat's test
// twice on each number with two different bases while doing modular exponentation.
//
// Then it's only a matter of binary search on the generated array.
//
////////////////////////////////////////////////////////////////////////////////////////
//
// REFERENCES and Prerequisites:
// -----------------------------
//
// Fermat's Primality Test : wikipedia
// Modular Exponentation : wikipedia
// Binary Search : find this anywhere XD
// Bitwise Shifting : Any standard book on C/C++ (Optional)
//
//////////////////////////////////////////////////////////////////////////////////////



long modPow(long base, long exponent, long mod){
    // This function calculates (base^exponent)%mod
    // This modular exponentation algorithm can be found on wikipedia

    long res = 1;
    base = base % mod;
    while(exponent > 0){
        if(exponent % 2 == 1) res = (res * base)%mod;
        exponent = exponent / 2;
        base = (base * base) % mod;
    }
    return res;
}

bool isPrime(long n){
    // see here how I used the Fermat's test with two bases (2 and 13) simultaneously
    // to make sure that any composite number does not get passed as a prime.

    return n==2 || n==3 || (modPow(2,n-1,n)==1 && modPow(13,n-1,n)==1);
}

bool isPalin(long n){
    // Check if the number is a palindrome
    // Very much trivial and easy implementation, just reverse the number and 
    // see if they are still equal

    long n1 = 0, n2 = n;
    while(n2){
        n1*=10;
        n1+=n2%10;
        n2/=10;
    }
    if(n1==n) return true;
    else return false;
}
 
int main(){
    for(int i=2; i<10050000; i++) if(isPrime(i)&&isPalin(i)) cout<<i<<",";
}
 
*/


///////////////////////////////////////////////////////////////////////////////////////


 
long arr[120]={ 1,2,3,5,7,11,101,131,151,181,191,313,353,373,383,727,757,787,797,
                919,929,10301,10501,10601,11311,11411,12421,12721,12821,13331,13831,
                13931,14341,14741,15451,15551,16061,16361,16561,16661,17471,17971,
                18181,18481,19391,19891,19991,30103,30203,30403,30703,30803,31013,
                31513,32323,32423,33533,34543,34843,35053,35153,35353,35753,36263,
                36563,37273,37573,38083,38183,38783,39293,70207,70507,70607,71317,
                71917,72227,72727,73037,73237,73637,74047,74747,75557,76367,76667,
                77377,77477,77977,78487,78787,78887,79397,79697,79997,90709,91019,
                93139,93239,93739,94049,94349,94649,94849,94949,95959,96269,96469,
                96769,97379,97579,97879,98389,98689,1003001 };
 
// There are just this many Prime Palindromes near and before 10^6. Now this is 
// the joke in the problem :D

int main() {
    long N;
    cin >> N;

    // Now just do a Binary Search on the array,
    // Linear search will work too, but why not use a faster approach when it's so much easy.

    int beg = 0, end = 115;
    int mid = (beg + end) >> 1; // '>>' is the Bitwise right shift operator. Right shifting once
                                // is equivalent to dividing the number by 2. 
                                // (beg+end)>>1 is same as (beg+end)/2, but shifting is always faster

    while(end > beg && end != beg+1){
        if(N<=arr[mid]) end = mid;
        else beg = mid; 
        mid = (beg + end) >> 1;
    }

    // and we have the solution. :)
    cout << arr[end] << endl;
    return 0;
}