LeetCode - Algorithms - 866. Prime Palindrome

Problem

866. Prime Palindrome

Java

Brute-force

Except for 11, all palindromic primes have an odd number of digits, because the divisibility test for 11 tells us that every palindromic number with an even number of digits is a multiple of 11.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
    public int primePalindrome(int n) {
        if (n <= 2) return 2;
        else if (n == 3) return 3;
        else if (n > 3 && n <= 5) return 5;
        else if (n > 5 && n <= 7) return 7;
        else if (n > 7 && n <= 11) return 11;
        else if (n >= 1e7 && n <= 1e8) return 100030001;
        else {
            int p = 101;
            for (int i = n; i < Integer.MAX_VALUE; i++) {
                if ((i & 1) == 1) {
                    int digits = (int) (Math.floor(Math.log10(i))) + 1;
                    if ((digits & 1) == 1) {
                        if (isPrime(i)) {
                            if (isPalindrome(i)) {
                                p = i;
                                break;
                            }
                        }
                    }
                }
            }
            return p;
        }        
    }
    
    private boolean isPrime(int n) {
        if (n < 2) return false;
        if (n == 2 || n == 3) return true;
        if (n % 2 == 0 || n % 3 == 0) return false;
        int sqrtN = (int) Math.sqrt(n) + 1;
        for (int i = 6; i <= sqrtN; i += 6) {
            if (n % (i - 1) == 0 || n % (i + 1) == 0) return false;
        }
        return true;
    }    
    
    private boolean isPalindrome(int x) {
        boolean b = false;
        int originalInteger = x;
        int reversedInteger = 0, remainder = 0;
        int t = x;
        while (t > 0) {
            remainder = t % 10;
            reversedInteger = reversedInteger * 10 + remainder;
            t /= 10;
        }
        if (originalInteger == reversedInteger)
            b = true;
        return b;
    }    
}

Submission Detail

  • 60 / 60 test cases passed.
  • Runtime: 1087 ms, faster than 5.56% of Java online submissions for Prime Palindrome.
  • Memory Usage: 35.5 MB, less than 97.78% of Java online submissions for Prime Palindrome.