Palindromes with even number of digits are divisible by 11. Let's start with increasing given N to number of the form abcdcba (palindrome with odd number of digits). Set of prime numbers is pretty dense and here we can expect something similar. I guess iterating over consecutive palindromes is a good idea. So I would suggest loop when first we increase d by one up to 9, then set d :  = 0 and increase c by one and so on. After every change we check if this number is prime in O(number of prime numbers up to ). In the beginning we must run sieve for numbers up to (or up to sth like , whatever).

And one more trick. If our current numbers is divisible e.g. by 25 or by 50 then we must change a or b (because we must change one of two last digits) so we shouldn't slowly increase d and c. We must do b +  = 1 in this case. So we have special case if our number has divisor which is also a divisor of 10^k.