# 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 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 nLength = to_string(n).length(); while (true) { for (const int num : getPalindromes(nLength)) if (num >= n && isPrime(num)) return num; ++nLength; } 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(reversedS.begin(), reversedS.end()); 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 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 nLength = String.valueOf(n).length(); while (true) { for (final int num : getPalindromes(nLength)) if (num >= n && isPrime(num)) return num; ++nLength; } } 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 nLength = len(str(n)) while True: for num in getPalindromes(nLength): if num >= n and isPrime(num): return num nLength += 1