หา Palindrome Prime ถัดไปด้วย C++

ภาพรวมปัญหา

ได้รับ N หาเลขที่เป็น Palindrome และ Prime พร้อมกัน ที่น้อยที่สุดและ > N

Palindrome: อ่านจากซ้าย-ขวาและขวา-ซ้ายได้เหมือนกัน (เช่น 101, 131)

Prime: มีตัวหารแค่ 1 และตัวมันเอง

ตัวอย่าง

อินพุต

N = 12

เอาต์พุต

101

คำอธิบาย

Palindrome > 12: 22, 33, 44, 55, 66, 77, 88, 99, 101...
Prime ในบรรดานี้: 101

วิธีแก้ปัญหา

ข้อสังเกตสำคัญ: Palindrome ที่มีหลักคู่ (ยกเว้น 11) หาร 11 ลงตัว → ไม่ใช่ Prime

ดังนั้นต้องสร้างเฉพาะ Palindrome หลักคี่ (และ 11)

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

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

bool isPrime(int num) {
    if (num < 2) return false;
    if (num == 2) return true;
    if (num % 2 == 0) return false;
    for (int i = 3; i * i <= num; i += 2)
        if (num % i == 0) return false;
    return true;
}

int primePalindrome(int N) {
    if (8 <= N && N <= 11) return 11;
    
    for (int x = 1; x < 100000; ++x) {
        string s = to_string(x);
        string rev = s;
        reverse(rev.begin(), rev.end());
        
        // สร้าง palindrome หลักคี่: xyzyx (ตัดตัวกลางซ้ำ)
        string palindromeStr = s + rev.substr(1);
        int y = stoi(palindromeStr);
        
        if (y >= N && isPrime(y))
            return y;
    }
    return -1;
}

int main() {
    int N = 432;
    cout << "The next prime palindrome is " << primePalindrome(N);
    return 0;
}

เอาต์พุต

The next prime palindrome is 929

สรุป

สร้าง Palindrome หลักคี่โดย mirror สตริง (ตัดตัวกลาง) แล้วเช็ค Prime ลดพื้นที่ค้นหามาก

หมายเหตุ: โค้ดต้นฉบับมี bug เรียกฟังก์ชันผิด ชื่อฟังก์ชันไม่ตรงกัน (findNextPrimePallindrome vs primePalindrome) แก้ไขแล้ว