Understand step-by-step | Runtime: 1ms | Time Space: O(log n + √n) & Space complexity: O(1)
Finds the smallest prime palindrome by using string manipulation for palindrome generation and a systematic approach to checking for primes. The use of mathemat
Finds the smallest prime palindrome by using string manipulation for palindrome generation and a systematic approach to checking for primes. The use of mathematical properties and optimizations, such as only generating half of the palindrome and checking divisibility up to the square root, makes it an effective solution.\n\n# Logic Flow\n- Handle special cases for small numbers.\n- Convert the number to a string and derive the starting point for palindrome generation.\n- Generate palindromes iteratively, starting from half the number and checking each palindrome for primality.\n- Return the first prime palindrome found, or -1 if none exists up to the limit.\n\n# Approach\n### Method: primePalindrome(int n)\nThis method returns the smallest prime palindrome that is greater than or equal to the input number `n`.\n\n**Logic:**\n1. **Special Cases:**  \n   - If `n` is between 8 and 11 (inclusive), return 11 directly, since it\u2019s the smallest prime palindrome in this range.\n\n2. **Convert Number to String:**  \n   - Convert `n` into a string to find its length and slice it for palindrome generation.\n\n3. **Starting Point:**  \n   - Determine the starting point for generating palindromes by taking the first half of `n`.\n\n4. **Generate Palindromes:**  \n   - Loop from the starting number up to 10003:\n     - Generate a palindrome using the `palindromeGen` method.\n     - Check if the generated palindrome is greater than or equal to `n` and if it is a prime number using the `isPrime` method.\n     - If both conditions are satisfied, return this palindrome.\n\n5. **Return -1:**  \n   - If no prime palindrome is found, return -1.\n\n---\n\n### Method: palindromeGen(int n)\nThis helper method generates a palindrome from a given number `n`.\n\n**How it works:**\n- The result starts with `n` itself.\n- In a loop, `n` is divided by `10` (effectively shifting digits to the right), and the last digit of `n` is obtained with `n % 10`.\n- This last digit is appended to `result`, effectively reversing the digits of `n` to create a palindrome.\n\n**Example:**\n- If `n = 123`, the function builds `result` as follows:\n- Start with `result = 123`.\n- After the first iteration: `result = 123 * 10 + 3 = 1230 + 3 = 1233`.\n- After the second iteration: `result = 1233 * 10 + 2 = 12330 + 2 = 12332`.\n- After the third iteration: `result = 12332 * 10 + 1 = 123320 + 1 = 123321`.\n- Thus, `palindromeGen(123)` returns `12321`.\n\n---\n\n### Method: isPrime(int n)\nThis helper method checks if a given number `n` is a prime number.\n\n**How it works**:\n1. Handle basic cases:\n   - Return `false` for numbers less than or equal to 1.\n   - Return `true` for 2 and 3 (the smallest prime numbers).\n2. Eliminate even numbers and multiples of 3:\n   - If `n` is divisible by 2 or 3, return `false`.\n3. Check for divisibility:\n   - Use a loop starting from 5, check up to the square root of `n`, skipping even numbers and multiples of 3.\n   - If `n` is divisible by any of these numbers, return `false`.\n4. If none of the above conditions are met, return `true`.\n\n\n# Complexity\n- Time complexity: O(log n + \u221An)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(1)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```java []\nclass Solution {\n    public int primePalindrome(int n) {\n        if (n >= 8 && n <= 11)\n            return 11;\n\n        String strN = Integer.toString(n);\n        int sliceIndex = (strN.length() + 1) / 2;\n        int start = Integer.parseInt(strN.substring(0, sliceIndex));\n\n        for (int i = start; i <= 10003; i++) {\n            int pd = palindromeGen(i);\n            if (pd >= n && isPrime(pd))\n                return pd;\n        }\n        return -1;\n    }\n\n    private int palindromeGen(int n) {\n\n        int result = n;\n        while ((n /= 10) != 0)\n            result = result * 10 + n % 10;\n        return result;\n    }\n\n    private boolean isPrime(int n) {\n        if (n <= 1)\n            return false;\n        if (n <= 3)\n            return true;\n        // Eliminate multiples of 2 and 3\n        if (n % 2 == 0 || n % 3 == 0)\n            return false;\n\n        // Check divisibility from 5 to \u221An, skipping even numbers and multiples of 3\n        for (int i = 5; i * i <= n; i += 6) {\n            if (n % i == 0 || n % (i + 2) == 0)\n                return false;\n        }\n        return true;\n    }\n\n}\n```
['Java']