Số nguyên tố đối xứng (palindrome) nhỏ nhất lớn hơn N C++

Cho số N, tìm số nguyên tố đối xứng (palindrome prime) nhỏ nhất > N.

Ví dụ

N=10 → 11
N=15 → 101 (vì 11, 101 là prime palindrome, 11 ≤ 15)

Thuật toán

• Từ N+1 kiểm tra từng số:
• Kiểm tra nguyên tố: thử chia đến √n.
• Kiểm tra palindrome: đảo số so sánh.
• Thỏa cả hai → trả về.

Triển khai C++

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

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

bool isPalindrome(int n) {
    int orig = n, rev = 0;
    while (n) { rev = rev * 10 + n % 10; n /= 10; }
    return orig == rev;
}

int nextPrimePalindrome(int n) {
    for (int i = n + 1; ; i++)
        if (isPrime(i) && isPalindrome(i)) return i;
}

int main() {
    cout << nextPrimePalindrome(15) << endl; // 101
    return 0;
}

Kết quả

101

Lưu ý: Code gốc có bug trong isPalindrome (gán n = num sai), đã sửa ở trên.