เลข Emirp (Emirp Numbers) ใน C++

Emirp Number คืออะไร?

Emirp (Prime สะกดย้อนกลับ) คือจำนวนเฉพาะที่เมื่อกลับลำดับหลักแล้ว ได้จำนวนเฉพาะอีกตัวหนึ่งที่ ต่างจากตัวเดิม

จำนวนเฉพาะที่เป็น Palindrome (เช่น 11, 101) และจำนวนเฉพาะหลักเดียว ไม่ใช่ Emirp

ตัวอย่าง Emirp: 13, 17, 31, 37, 71, 73, 79, 97, ...

โปรแกรมพิมพ์ Emirp Numbers น้อยกว่า n

#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 findAllEmirpNumber(int n) {
    vector<bool> isPrime(n + 1, true);
    isPrime[0] = isPrime[1] = false;
    for (int p = 2; p * p <= n; p++)
        if (isPrime[p])
            for (int i = p * 2; i <= n; i += p)
                isPrime[i] = false;
    
    for (int p = 2; p <= n; p++) {
        if (isPrime[p]) {
            int rev = reverseDigits(p);
            if (p != rev && rev <= n && isPrime[rev]) {
                cout << p << " ";
                isPrime[rev] = false;  // กันซ้ำ
            }
        }
    }
}

int main() {
    int n = 40;
    cout << "Emirp numbers <= " << n << ": ";
    findAllEmirpNumber(n);
    return 0;
}

ผลลัพธ์

Emirp numbers <= 40: 13 17 31 37