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.

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;
    }
}

############

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;
    }
}

// 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;
    }
};

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

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++
	}
}

866 - Prime Palindrome

866. Prime Palindrome (Medium)

Solution 1.

All Problems

All Solutions

Welcome to Subscribe On Youtube

866. Prime Palindrome (Medium)

Solution 1.

All Problems

All Solutions