Find the smallest palindrome number which is prime too and greater then given number N.
Input : N = 7 Output :11 11 is the smallest palindrome prime which is greater than N. Input : N = 112 Output : 131
An efficient solution is based on below observations. All palindrome with even digits is multiple of 11.
We can prove as follow:
11 % 11 = 0
1111 % 11 = 0
111111 % 11 = 0
11111111 % 11 = 0
1001 % 11 = (1111 – 11 * 10) % 11 = 0
100001 % 11 = (111111 – 1111 * 10) % 11 = 0
10000001 % 11 = (11111111 – 111111 * 10) % 11 = 0
For any palindrome with even digits:
abcddcba % 11
= (a * 10000001 + b * 100001 * 10 + c * 1001 * 100 + d * 11 * 1000) % 11
All palindrome with even digits is multiple of 11.
So among them, 11 is the only one prime
if (8 <= N <= 11) return 11
For other, we consider only palindrome with odd digits.
- Next smallest prime palindrome
- Quick ways to check for Prime and find next Prime in Java
- Find coordinates of a prime number in a Prime Spiral
- Given a number, find the next smallest palindrome
- Find the player who rearranges the characters to get a palindrome string first
- Sentence Palindrome (Palindrome after removing spaces, dots, .. etc)
- Find index i such that prefix of S1 and suffix of S2 till i form a palindrome when concatenated
- Find minimum number of merge operations to make an array palindrome
- Find if nCr is divisible by the given prime
- Given a number x , find y such that x*y + 1 is not a prime
- Find the XOR of first N Prime Numbers
- Find two prime numbers with given sum
- Find the prime P using given four integers
- Count all palindrome which is square of a palindrome
- Find the sum of prime numbers in the Kth array
If you like GeeksforGeeks and would like to contribute, you can also write an article using contribute.geeksforgeeks.org or mail your article to firstname.lastname@example.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.
Please Improve this article if you find anything incorrect by clicking on the "Improve Article" button below.