Tìm số nguyên tố đối xứng (palindrome prime) tiếp theo trong C++

Giới thiệu

Cho số nguyên N. Tìm số nguyên tố đối xứng (palindrome prime) nhỏ nhất lớn hơn N.

Số đối xứng: Đọc xuôi và ngược giống nhau. Số nguyên tố: Chỉ có ước 1 và chính nó.

Ví dụ minh họa

Đầu vào

N = 12

Đầu ra

101

Giải thích

Các palindrome > 12: 22, 33, 44, 55, 66, 77, 88, 99, 101...
Trong đó chỉ 101 là số nguyên tố.

Phương pháp giải

Quan sát: Tất cả palindrome có số chữ số chẵn đều chia hết cho 11 (trừ 11). Do đó chỉ cần kiểm tra palindrome số chữ số lẻ.

Sinh palindrome số chữ số lẻ: lấy x, đảo ngược bỏ ký tự đầu, nối lại. VD: x=12 → "12" + "1" = "121".

Chương trình minh họa

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

bool isPrime(int num) {
    if (num < 2 || num % 2 == 0) return num == 2;
    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 r(s.rbegin(), s.rend());
        int y = stoi(s + r.substr(1)); // palindrome lẻ
        if (y >= N && isPrime(y))
            return y;
    }
    return -1;
}

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

Đầu ra

The next prime palindrome is 757

Lưu ý: Output mẫu trong nội dung gốc bị nhầm lẫn với bài toán khác.