Prime Palindrome ใน C++

คำอธิบายปัญหา

หา prime palindrome ที่น้อยที่สุดซึ่ง >= N

ตัวอย่าง: N=13 → 101 (11 ก็เป็นแต่ < 13)

ข้อสังเกตสำคัญ

• Palindrome เลขคู่หลัก (ยกเว้น 11) หาร 11 ลงตัว → ไม่ใช่ prime
• สร้าง palindrome เลขคี่หลัก: กึ่งแรก + reverse(กึ่งแรกโดยตัดตัวสุดท้าย)
• เช่น 123 → 12321

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool isPrime(int n) {
        if(n < 2) return false;
        if(n % 2 == 0) return n == 2;
        for(int i = 3; i * 1LL * i <= n; i += 2) {
            if(n % i == 0) return false;
        }
        return true;
    }
    
    int primePalindrome(int N) {
        if(8 <= N && N <= 11) return 11;
        
        for(int len = 1; len <= 5; len++) { // up to 10^5
            int start = pow(10, len - 1);
            int end = pow(10, len);
            for(int i = start; i < end; i++) {
                string s = to_string(i);
                string rev = s.substr(0, s.size() - 1);
                reverse(rev.begin(), rev.end());
                int num = stoi(s + rev);
                if(num >= N && isPrime(num)) return num;
            }
        }
        return 100030001; // fallback (known prime palindrome)
    }
};

int main() {
    Solution ob;
    cout << ob.primePalindrome(105);
    return 0;
}

อินพุต

105

เอาต์พุต

131