# 866. Prime Palindrome

• Time:
• Space:
  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 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 class Solution { public: int primePalindrome(int N) { if (N <= 2) return 2; if (N == 3) return 3; if (N <= 5) return 5; if (N <= 7) return 7; if (N <= 11) return 11; int n = to_string(N).length(); while (true) { for (const int num : getPalindromes(n)) if (num >= N && isPrime(num)) return num; ++n; } throw; } private: vector getPalindromes(int n) { vector palindromes; const int length = n / 2; for (int i = pow(10, length - 1); i < pow(10, length); ++i) { const string s = to_string(i); string reversedS = s; reverse(begin(reversedS), end(reversedS)); for (int j = 0; j < 10; ++j) palindromes.push_back(stoi(s + to_string(j) + reversedS)); } return palindromes; } bool isPrime(int num) { for (int i = 2; i < sqrt(num) + 1; ++i) if (num % i == 0) return false; return true; } }; 
  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 36 37 38 39 40 41 42 43 44 45 class Solution { public int primePalindrome(int N) { if (N <= 2) return 2; if (N == 3) return 3; if (N <= 5) return 5; if (N <= 7) return 7; if (N <= 11) return 11; int n = String.valueOf(N).length(); while (true) { for (int num : getPalindromes(n)) if (num >= N && isPrime(num)) return num; ++n; } } private List getPalindromes(int n) { List palindromes = new ArrayList<>(); int length = n / 2; for (int i = (int) Math.pow(10, length - 1); i < (int) Math.pow(10, length); ++i) { String s = String.valueOf(i); String reversedS = new StringBuilder(s).reverse().toString(); for (int j = 0; j < 10; ++j) palindromes.add(Integer.valueOf(s + String.valueOf(j) + reversedS)); } return palindromes; } private boolean isPrime(int num) { for (int i = 2; i < (int) Math.sqrt(num) + 1; ++i) if (num % i == 0) return false; return true; } } 
  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 class Solution: def primePalindrome(self, N: int) -> int: def getPalindromes(n: int) -> int: length = n // 2 for i in range(10**(length - 1), 10**length): s = str(i) for j in range(10): yield int(s + str(j) + s[::-1]) def isPrime(num: int) -> bool: return not any(num % i == 0 for i in range(2, int(num**0.5 + 1))) if N <= 2: return 2 if N == 3: return 3 if N <= 5: return 5 if N <= 7: return 7 if N <= 11: return 11 n = len(str(N)) while True: for num in getPalindromes(n): if num >= N and isPrime(num): return num n += 1