Formatted question description: https://leetcode.ca/all/866.html

866. Prime Palindrome (Medium)

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.

Related Topics:
Math

Solution 1.

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

// Time: O(N)
// Space: O(logN)
// Ref: https://leetcode.com/problems/prime-palindrome/solution/
class Solution {
    bool isPrime(int x) {
        if (x < 2) return false;
        for (int d = 2, R = sqrt(x); d <= R; ++d) {
            if (x % d == 0) return false;
        }
        return true;
    }
public:
    int primePalindrome(int N) {
        for (int L = 1; L <= 5; ++L) {
            for (int root = pow(10, L - 1); root < pow(10, L); ++root) { // check for odd-length palindromes
                auto s = to_string(root);
                for (int k = L - 2; k >= 0; --k) s += s[k];
                int x = stoi(s);
                if (x >= N && isPrime(x)) return x;
            }
            for (int root = pow(10, L - 1); root < pow(10, L); ++root) {
                auto s = to_string(root);
                for (int k = L - 1; k >= 0; --k) s += s[k];
                int x = stoi(s);
                if (x >= N && isPrime(x)) return x;
            }
        }
        return -1;
    }
};

Solution 2. Brute Force with Mathematical Shortcut

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

// Time: O(N)
// Space: O(1)
// Ref: https://leetcode.com/problems/prime-palindrome/solution/
class Solution {
    bool isPrime(int x) {
        if (x < 2) return false;
        for (int d = 2, R = sqrt(x); d <= R; ++d) {
            if (x % d == 0) return false;
        }
        return true;
    }
    int reverse(int N) {
        int ans = 0;
        while (N > 0) {
            ans = 10 * ans + (N % 10);
            N /= 10;
        }
        return ans;
    }
public:
    int primePalindrome(int N) {
        while (true) {
            if (N == reverse(N) && isPrime(N)) return N;
            ++N;
            if (1e7 < N && N < 1e8) N = 1e8;
        }
    }
};

Java

  • class Solution {
        public int primePalindrome(int N) {
            int palindromeNum = nextPalindrome(N);
            while (!isPrime(palindromeNum))
                palindromeNum = nextPalindrome(palindromeNum + 1);
            return palindromeNum;
        }
    
        public int nextPalindrome(int num) {
            int length = String.valueOf(num).length();
            if (num + 1 == (int) Math.pow(10, length))
                return num + 2;
            int divisor = (int) Math.pow(10, length / 2);
            int headerNum = num / divisor;
            boolean even = length % 2 == 0;
            int palindromeNum = generatePalindrome(headerNum, even);
            if (palindromeNum < num)
                palindromeNum = generatePalindrome(headerNum + 1, even);
            return palindromeNum;
        }
    
        public int generatePalindrome(int num, boolean even) {
            StringBuffer sb1 = new StringBuffer(String.valueOf(num));
            StringBuffer sb2 = new StringBuffer(String.valueOf(num));
            sb2.reverse();
            if (!even)
                sb2.deleteCharAt(0);
            String palindromeStr = new StringBuffer(sb1.toString()).append(sb2.toString()).toString();
            return Integer.parseInt(palindromeStr);
        }
    
        public boolean isPrime(int num) {
            if (num == 1)
                return false;
            if (num == 2 || num == 3)
                return true;
            if (num % 2 == 0 || num % 3 == 0)
                return false;
            int sqrt = (int) Math.sqrt(num);
            for (int i = 5; i <= sqrt; i += 2) {
                if (num % i == 0)
                    return false;
            }
            return true;
        }
    }
    
  • // OJ: https://leetcode.com/problems/prime-palindrome/
    // Time: O(N)
    // Space: O(logN)
    // Ref: https://leetcode.com/problems/prime-palindrome/solution/
    class Solution {
        int getPalindrome(int half, bool odd) {
            string s = to_string(half);
            for (int i = s.size() - 1 - odd; i >= 0; --i) s += s[i];
            return stoi(s);
        }
        bool isPrime(int n) {
            if (n < 2) return false;
            for (int d = 2; d * d <= n; ++d) {
                if (n % d == 0) return false;
            }
            return true;
        }
    public:
        int primePalindrome(int n) {
            for (int len = 1; len <= 5; ++len) {
                for (int root = pow(10, len - 1); root < pow(10, len); ++root) { // Enumerate odd-length palindromes
                    int pal = getPalindrome(root, true);
                    if (pal >= n && isPrime(pal)) return pal;
                }
                for (int root = pow(10, len - 1); root < pow(10, len); ++root) { // Enumerate even-length palindromes
                    int pal = getPalindrome(root, false);
                    if (pal >= n && isPrime(pal)) return pal;
                }
            }
            return -1;
        }
    };
    
  • print("Todo!")
    

All Problems

All Solutions