题目

求出大于或等于 N 的最小回文素数。

回顾一下，如果一个数大于 1，且其因数只有 1 和它自身，那么这个数是素数。

例如，2，3，5，7，11 以及 13 是素数。

回顾一下，如果一个数从左往右读与从右往左读是一样的，那么这个数是回文数。

例如，12321 是回文数。

示例 1：输入：6 输出：7

示例 2：输入：8 输出：11

示例 3：输入：13 输出：101

提示：1 <= N <= 10^8

答案肯定存在，且小于 2 * 10^8。

解题思路分析

1、*力暴**法；时间复杂度O(n^(1/2))，空间复杂度O(1)

func primePalindrome(N int) int {
   if 8 <= N && N <= 11 { // 特判：偶数位的回文数都可以被11整除
      return 11
   }
   for i := 1; i < 100000; i++ {
      s := strconv.Itoa(i)
      temp := []byte(s)
      for i := 0; i < len(s)/2; i++ {
         temp[i], temp[len(s)-1-i] = temp[len(s)-1-i], temp[i]
      }
      target, _ := strconv.Atoi(s + string(temp[1:]))
      if target >= N && isPrime(target) {
         return target
      }
   }
   return -1
}

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

总结

Medium题目，直接遍历容易超时，注意优化