Question

866. 回文质数

English Version

题目描述

给你一个整数 n ，返回大于或等于 n 的最小回文质数。

一个整数如果恰好有两个除数：1 和它本身，那么它是 质数 。注意，1 不是质数。

• 例如，2、3、5、7、11 和 13 都是质数。

一个整数如果从左向右读和从右向左读是相同的，那么它是 回文数 。

• 例如，101 和 12321 都是回文数。

测试用例保证答案总是存在，并且在 [2, 2 * 108] 范围内。

 

示例 1：

输入：n = 6
输出：7

示例 2：

输入：n = 8
输出：11

示例 3：

输入：n = 13
输出：101

 

提示：

• 1 <= n <= 108

解法

方法一

class Solution:
  def primePalindrome(self, n: int) -> int:
    def is_prime(x):
      if x < 2:
        return False
      v = 2
      while v * v <= x:
        if x % v == 0:
          return False
        v += 1
      return True

    def reverse(x):
      res = 0
      while x:
        res = res * 10 + x % 10
        x //= 10
      return res

    while 1:
      if reverse(n) == n and is_prime(n):
        return n
      if 10**7 < n < 10**8:
        n = 10**8
      n += 1

class Solution {
  public int primePalindrome(int n) {
    while (true) {
      if (reverse(n) == n && isPrime(n)) {
        return n;
      }
      if (n > 10000000 && n < 100000000) {
        n = 100000000;
      }
      ++n;
    }
  }

  private boolean isPrime(int x) {
    if (x < 2) {
      return false;
    }
    for (int v = 2; v * v <= x; ++v) {
      if (x % v == 0) {
        return false;
      }
    }
    return true;
  }

  private int reverse(int x) {
    int res = 0;
    while (x != 0) {
      res = res * 10 + x % 10;
      x /= 10;
    }
    return res;
  }
}

class Solution {
public:
  int primePalindrome(int n) {
    while (1) {
      if (reverse(n) == n && isPrime(n)) return n;
      if (n > 10000000 && n < 100000000) n = 100000000;
      ++n;
    }
  }

  bool isPrime(int x) {
    if (x < 2) return false;
    for (int v = 2; v * v <= x; ++v)
      if (x % v == 0)
        return false;
    return true;
  }

  int reverse(int x) {
    int res = 0;
    while (x) {
      res = res * 10 + x % 10;
      x /= 10;
    }
    return res;
  }
};

func primePalindrome(n int) int {
  isPrime := func(x int) bool {
    if x < 2 {
      return false
    }
    for v := 2; v*v <= x; v++ {
      if x%v == 0 {
        return false
      }
    }
    return true
  }

  reverse := func(x int) int {
    res := 0
    for x != 0 {
      res = res*10 + x%10
      x /= 10
    }
    return res
  }
  for {
    if reverse(n) == n && isPrime(n) {
      return n
    }
    if n > 10000000 && n < 100000000 {
      n = 100000000
    }
    n++
  }
}