866.Prime-Palindrome.md

866. Prime Palindrome

---

题目地址

https://leetcode.com/problems/prime-palindrome/

题目描述

Find the smallest prime palindrome greater than or equal to N.

Recall that a number is prime if it's only divisors are 1 and itself, and it is greater than 1. 

For example, 2,3,5,7,11 and 13 are primes.

Recall that a number is a palindrome if it reads the same from left to right as it does from right to left. 

For example, 12321 is a palindrome.

Example 1:

Input: 6
Output: 7

Example 2:
Input: 8
Output: 11

Example 3:
Input: 13
Output: 101

Note:
1 <= N <= 10^8
The answer is guaranteed to exist and be less than 2 * 10^8.

代码

Approach 1: Iterate Palindromes

class Solution {
    public int primePalindrome(int N) {
    for (int L = 1; L <= 5; L++) {
      for (int root = (int)Math.pow(10, L - 1); root < (int)Math.pow(10, L); root++) {
        StringBuilder sb = new StringBuilder(Integer.toString(root));
        for (int k = L - 2; k >= 0; k--) {
          sb.append(sb.charAt(k));
        
          if (x >= N && isPrime(x)) {
            return x;
          }
        }

        for (int root = (int)Math.pow(10, L - 1); root < (int)Math.pow(10, L); root++) {
          StringBuilder sb = new StringBuilder(Integer.toString(root));
          for (int k = L - 1; k >= 0; k--) {
            sb.append(sb.charAt(k));
          }

          int x = Integer.valueOf(sb.toString());
          if (x >= N && isPrime(x)) {
            return x;
          }
        }
      }
    }

    throw null;
  }

  public boolean isPrime(int N) {
    if (N < 2) return false;
    int R = (int) Math.sqrt(N);
    for (int d = 2; d <= R; d++) {
      if (N % d == 0)    return false;
    }
    return true;
  }

}

Approach 2 Brute Force with Mathematical Shortcut

class Solution {
    public int primePalindrome(int N) {
        while (true) {
            if (N == reverse(N) && isPrime(N))
                return N;
            N++;
          //all 8 digit palindromes are not prime, so we can skip all 8 digit numbers.
            if (10_000_000 < N && N < 100_000_000)
                N = 100_000_000;
        }
    }

    public boolean isPrime(int N) {
        if (N < 2) return false;
        int R = (int) Math.sqrt(N);
        for (int d = 2; d <= R; ++d)
            if (N % d == 0) return false;
        return true;
    }

    public int reverse(int N) {
        int ans = 0;
        while (N > 0) {
            ans = 10 * ans + (N % 10);
            N /= 10;
        }
        return ans;
    }
}