Tìm số nguyên tố đặc biệt lớn nhất ≤ N trong C++

Số nguyên tố đặc biệt (special prime) là số mà khi cắt bỏ lần lượt các chữ số cuối, các số còn lại đều là số nguyên tố. Ví dụ: 379 → 379, 37, 3 đều là nguyên tố.

Dùng sàng Eratosthenes tạo mảng đánh dấu nguyên tố đến N. Duyệt giảm từ N, kiểm tra xem số đó có phải special prime không (kiểm tra từng tiền tố bằng chia 10 liên tiếp).

Ví dụ

#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;
        } else N--;
    }
}

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

Kết quả

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