Số Emirp (Emirp Numbers) trong C++

Số Emirp (Prime viết ngược) là số nguyên tố mà khi viết ngược các chữ số lại được một số nguyên tố khác (khác với số ban đầu).

Ví dụ: 13 -> 31 (cả hai đều nguyên tố). 11 không phải Emirp (viết ngược vẫn 11 - palindromic prime). Các số nguyên tố 1 chữ số không phải Emirp.

Ví dụ

Đầu vào: n = 40

Đầu ra: 13, 17, 31, 37

Phương pháp giải - Sàng Eratosthenes

1. Dùng Sàng Eratosthenes tìm tất cả số nguyên tố ≤ n (hoặc ≤ max(n, reversed(n))).
2. Duyệt các số nguyên tố p.
3. Đảo ngược chữ số của p thành rev.
4. Nếu p != rev VÀ rev là nguyên tố => p là Emirp.
5. Đánh dấu rev đã xử lý để không in trùng lặp (ví dụ in 13 và 31 cùng một cặp).

Chương trình minh họa

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

int reverseDigits(int x) {
    int rev = 0;
    while (x > 0) {
        rev = rev * 10 + x % 10;
        x /= 10;
    }
    return rev;
}

void findEmirp(int n) {
    // Giới hạn sàng cần đủ lớn để chứa cả số đảo ngược (ví dụ n=1000 -> rev có thể 9999)
    // Ở đây dùng MAX = 100000 cho an toàn
    const int LIMIT = 100000; 
    vector<bool> isPrime(LIMIT + 1, true);
    isPrime[0] = isPrime[1] = false;
    for (int p = 2; p * p <= LIMIT; p++)
        if (isPrime[p])
            for (int i = p * p; i <= LIMIT; i += p)
                isPrime[i] = false;

    cout << "Cac so Emirp <= " << n << ": ";
    for (int p = 2; p <= n; p++) {
        if (isPrime[p]) {
            int rev = reverseDigits(p);
            if (p != rev && rev <= LIMIT && isPrime[rev]) {
                cout << p << " ";
                // Đánh dấu rev để không in lại khi duyệt đến rev (nếu rev <= n)
                if (rev <= n) isPrime[rev] = false; 
            }
        }
    }
}

int main() {
    int n = 100;
    findEmirp(n);
    return 0;
}

Đầu ra

Cac so Emirp <= 100: 13 17 31 37 71 73 79 97