866

866. Prime Palindrome (Medium)

Given an integer n, return the smallest prime palindrome greater than or equal to n.

An integer is prime if it has exactly two divisors: 1 and itself. Note that 1 is not a prime number.

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

An integer is a palindrome if it reads the same from left to right as it does from right to left.

• For example, 101 and 12321 are palindromes.

The test cases are generated so that the answer always exists and is in the range [2, 2 * 108].

 

Example 1:

Input: n = 6
Output: 7

Example 2:

Input: n = 8
Output: 11

Example 3:

Input: n = 13
Output: 101

 

Constraints:

• 1 <= n <= 108

Related Topics:
Math

Similar Questions:

• Sum of k-Mirror Numbers (Hard)

Solution 1. Enumerate Palindromes

Enumerate palindromes and return the first one that is >= n and is a prime.

// OJ: https://leetcode.com/problems/prime-palindrome/
// Author: github.com/lzl124631x
// 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;
    }
};

Or

// OJ: https://leetcode.com/problems/prime-palindrome/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
    int getPalindrome(int half, bool odd) {
        int ans = half;
        if (odd) half /= 10;
        for (; half; half /= 10) ans = ans * 10 + half % 10;
        return ans;
    }
    bool isPrime(int n) {
        if (n == 1) return false;
        for (int i = 2; i * i <= n; ++i) {
            if (n % i == 0) return false;
        }
        return true;
    }
public:
    int primePalindrome(int n) {
        for (int len = log10(n) + 1; true; ++len) {
            int half = pow(10, (len - 1) / 2), end = half * 10;
            for (; half < end; ++half) {
                int pal = getPalindrome(half, len % 2);
                if (pal >= n && isPrime(pal)) return pal;
            }
        }
        return 0;
    }
};

Solution 2. Brute Force with Mathematical Shortcut

All even-digit palindromes, except for 11, are not primes because they are divisible by 11. For example, 2332 / 11 = 212

// OJ: https://leetcode.com/problems/prime-palindrome/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
// Ref: https://leetcode.com/problems/prime-palindrome/solution/
class Solution {
    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;
    }
    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;
        }
    }
};

Another way for primePalindrome

int digits(int n) {
    return (int)log10(n) + 1;
}
int primePalindrome(int n) {
    while (true) {
        if (n == reverse(n) && isPrime(n)) return n;
        ++n;
        if (n > 11 && digits(n) % 2 == 0) n = pow(10, digits(n));
    }
}