Problem
Find the smallest prime palindrome greater than or equal to N
.
Recall that a number is prime if it’s only divisors are 1 and itself, and it is greater than 1.
For example, 2,3,5,7,11 and 13 are primes.
Recall that a number is a palindrome if it reads the same from left to right as it does from right to left.
For example, 12321 is a palindrome.
Example 1:
Input: 6 Output: 7
Example 2:
Input: 8 Output: 11
Example 3:
Input: 13 Output: 101
Note:
1 <= N <= 10^8
- The answer is guaranteed to exist and be less than
2 * 10^8
.
Solution: Math
All odd digits palindromes have a factor 11, they are not prime except 11 itself.
Time complexity: O(n)
Space complexity: O(1)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
// Author: Huahua // Running time: 8 ms class Solution { public: int primePalindrome(int N) { if (N <= 2) return 2; if (N % 2 == 0) ++N; while (true) { if (reverse(N) == N && isPrime(N)) return N; N += 2; if (N > 11 & (int)log10(N) % 2 == 1) // 13 -> 101 // 1001 -> 10001 N = pow(10, (int)log10(N) + 1) + 1; } return -1; } private: int reverse(int n) { int r = 0; while (n) { r = 10 * r + n % 10; n /= 10; } return r; } bool isPrime(int n) { if (n <= 1) return false; for (int i = 2; i <= sqrt(n); ++i) if (n % i == 0) return false; return true; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment