Skip to content

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<int> getPalindromes(int n) {
    vector<int> 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;
      ranges::reverse(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
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<Integer> getPalindromes(int n) {
    List<Integer> 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