หา Special Prime ่ที่ใหญ่ที่สุดและไม่เกิน N ใน C++

Special Prime คือจำนวนเฉพาะที่เมื่อนำตัวเลขทิ้งทีละหลักจากขวาไปซ้าย ทุกขั้นตอนต้องเป็นจำนวนเฉพาะเสมอ

ตัวอย่าง: 379 เป็น Special Prime เพราะ 379, 37, 3 ล้วนเป็นจำนวนเฉพาะ

อัลกอริทึม

1. ใช้ Sieve of Eratosthenes สร้างตารางจำนวนเฉพาะ עד N
2. ตรวจสอบจาก N ลงมาจนกว่าจะเจอ Special Prime
3. การตรวจสอบ: แบ่งตัวเลขด้วย 10 ซ้ำๆ ตรวจสอบทุกค่าว่าเป็นเฉพาะทั้งหมด

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

#include <iostream>
using namespace std;

bool isSpecialPrime(bool sieve[], int num) {
    while (num) {
        if (!sieve[num])
            return false;
        num /= 10;
    }
    return true;
}

void findSpecialPrime(int N) {
    bool sieve[N + 10];
    for (int i = 0; i < N + 10; i++)
        sieve[i] = true;

    sieve[0] = sieve[1] = false;
    for (long long i = 2; i <= N; i++) {
        if (sieve[i]) {
            for (long long j = i * i; j <= N; j += i)
                sieve[j] = false;
        }
    }

    while (true) {
        if (isSpecialPrime(sieve, N)) {
            cout << N << '\n';
            break;
        }
        N--;
    }
}

int main() {
    cout << "Special prime in range (2 -> 400): ";
    findSpecialPrime(400);
    cout << "Special prime in range (2 -> 100): ";
    findSpecialPrime(100);
    return 0;
}

ผลลัพธ์

Special prime in range (2 -> 400): 379
Special prime in range (2 -> 100): 79

หมายเหตุ

Special Prime เรียกอีกอย่างว่า Truncatable Prime (จากซ้ายไปขวา) หรือ Right-truncatable Prime