Hiểu bài toán

Đề bài yêu cầu tìm tất cả các 'số siêu nguyên tố' có đúng n chữ số. Một số được gọi là siêu nguyên tố nếu nó là số nguyên tố và khi bỏ đi một số lượng bất kỳ các chữ số ở bên phải thì phần còn lại vẫn là một số nguyên tố. Ví dụ, 7331 là siêu nguyên tố vì 733, 73, và 7 đều là số nguyên tố. N là số nguyên dương nằm trong khoảng từ 1 đến 10. Đầu ra là danh sách các số siêu nguyên tố này, cách nhau bởi dấu cách.

Các cách tiếp cận

Cách Quay lui (Backtracking) kết hợp kiểm tra từng số

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

int n;
int X[100005] = {0};
int A[] = {1, 2, 3, 5, 7, 9};
int x = 0;

// Hàm kiểm tra số nguyên tố
bool isPrime(int x) {
    if (x == 1) return false;
    if (x == 2) return true;
    for (int i = 2; i <= sqrt(x); i++) {
        if (x % i == 0) return false;
    }
    return true;
} 

// Hàm kiểm tra điều kiện số siêu nguyên tố
bool check(int v, int k) {
    if (k == 1) {
        if (v == 2 || v == 3 || v == 5 || v == 7) return true;
    }
    if (v == 2 || v == 5) return false;
    if (isPrime(10*x+v)) return true;
    return false;
}

// Hàm quay lui sinh dãy số
void Try(int k) {
    for (int v : A) {
        if (check(v, k)) {
            X[k] = v;
            int old_x = x;
            x = 10*x + X[k];
            if (k == n) {
                for (int i = 1; i <= n; i++) cout << X[i];
                cout << " ";
            } else {
                Try(k+1);
            }
            x = old_x;
        }
    }
}

int main() {
    cin >> n;
    Try(1);
    return 0;
}

• Time Complexity: O(4 * 3^(n-1) * sqrt(M)), với M là số lớn nhất cần kiểm tra (khoảng 10^n).
• Space Complexity: O(n)

Thuật toán sử dụng phương pháp quay lui để dựng từng số siêu nguyên tố từ trái sang phải. Mảng A[] chứa các chữ số có thể dùng (1, 2, 3, 5, 7, 9). Hàm check(v, k) đảm bảo chữ số v ở vị trí thứ k thỏa mãn:

1. Nếu là chữ số đầu tiên (k=1), nó phải là 2, 3, 5, 7.
2. Nếu chữ số trước đó là 2 hoặc 5, không thể thêm chữ số nào (vì số 2-digit kết thúc bằng 2 hoặc 5 là chẵn hay bội của 5, không nguyên tố).
3. Nếu không, số mới tạo thành (bằng cách thêm v vào dãy số hiện tại) phải là số nguyên tố.

Hàm Try(k) thử tất cả các chữ số trong A[] cho vị trí thứ k. Nếu hợp lệ, nó đệ quy cho vị trí tiếp theo. Nếu đã đủ n chữ số, nó in ra kết quả.

Cách Quay lui tối ưu (Backtracking)

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

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

int n;
vector<int> result;

void backtrack(int current, int digits) {
    if (digits == n) {
        result.push_back(current);
        return;
    }

    static int nextDigits[] = {1, 3, 7, 9};

    for (int d : nextDigits) {
        int num = current * 10 + d;
        if (isPrime(num)) {
            backtrack(num, digits + 1);
        }
    }
}

int main() {
    cin >> n;
    int start[] = {2, 3, 5, 7};
    for (int s : start)
        if (n >= 1)
            backtrack(s, 1);

    for (int x : result)
        cout << x << " ";
    return 0;
}

• Time Complexity: O(4 * 3^(n-1) * sqrt(M))
• Space Complexity: O(n)

Đây là phiên bản tối ưu hơn của phương pháp quay lui.

1. Tối ưu số bắt đầu: Chỉ bắt đầu với các số 2, 3, 5, 7 (các số nguyên tố 1 chữ số).
2. Tối ưu chữ số tiếp theo: Sau chữ số đầu tiên, chỉ có thể thêm các chữ số 1, 3, 7, 9. Lý do:
   • Thêm 0, 2, 4, 5, 6, 8 vào một số nguyên tố (đang có chữ số đầu tiên là 2, 3, 5, 7) sẽ tạo ra số chẵn hoặc số chia hết cho 5 (trừ trường hợp số 2-5, nhưng 25, 52, 55... đều không nguyên tố).
   • Thêm 5 vào một số nguyên tố (khác 5) sẽ tạo ra số chia hết cho 5 (vì số đó > 5).
   • Thêm số chẵn vào một số nguyên tố lẻ sẽ tạo ra số chẵn.

Tuy nhiên, đoạn code mẫu này có một sai sót logic nhỏ: với n=1, nó vẫn gọi backtrack với nextDigits nhưng trong backtrack nó chỉ in ra nếu digits == n. Với n=1, vòng lặp start sẽ in ra các số 2, 3, 5, 7. Với n > 1, nó sẽ sinh ra các số có 2 chữ số trở lên. Nhưng đoạn code này không xử lý triệt để việc chỉ các chữ số 1, 3, 7, 9 được phép theo sau số 2 và 5.

Điểm khác biệt chính so với Solution 1 là cách tổ chức code: Solution 1 kiểm tra điều kiện trực tiếp trong hàm check và sử dụng mảng X để lưu dãy, trong khi Solution 2 này (thực ra là Solution 1 của bài nộp) sử dụng biến x toàn cục để lưu giá trị số hiện tại và X[] để in.

Cách Quay lui với kiểm tra trực tiếp (Backtracking with prefix check)

#include <bits/stdc++.h>
using namespace std;
short int n;
long long d = 0;
int a[4] = {2 , 3 , 5 , 7};
int b[4] = {1 , 3 , 7 , 9};
vector<long long> kq;

bool check(long long n) {
    if (n == 2) return true;
    if (n < 2 || n % 2 == 0) return false;
    for (int i = 3; i <= sqrt(n); i += 2)
        if (n % i == 0) return false;
    return true;
}

void backtrack(long long num, int l) {
    if (!check(num)) return;
    if (l == n - 1) {
        if (check(num)) kq.push_back(num);
        return;
    }
    for (int i = 0; i < 4; ++i) {
        long long idk = num * 10 + b[i];
        backtrack(idk, l + 1);
    }
}

int main() {
    cin >> n;
    for (int i = 0; i < 4; ++i)
        backtrack(a[i], 0);
    for (int i = 0; i < kq.size(); ++i)
        cout << kq[i] << ' ';
    return 0;
}

• Time Complexity: O(4 * 3^(n-1) * sqrt(M))
• Space Complexity: O(n)

Thuật toán này sử dụng quay lui để sinh các số.

1. Bắt đầu: Duyệt qua các số 2, 3, 5, 7 làm số bắt đầu.
2. Đệ quy: Hàm backtrack(num, l) nhận một số num và độ dài l (tính bằng số chữ số).
   • l trong code này là chỉ số của chữ số cuối cùng (0-indexed). Nếu n=3, l chạy từ 0 đến 1. Khi l == n - 1, số có đủ n chữ số.
   • Tại mỗi bước, nó thử thêm các chữ số từ mảng b (1, 3, 7, 9) vào bên phải số hiện tại.
   • Nó chỉ đệ quy tiếp nếu số mới tạo thành (idk) vẫn là số nguyên tố.

Đây là cách tiếp cận trực quan nhất và được tối ưu hóa khá tốt về mặt search space (không thử các chữ số không cần thiết). Logic "Nếu số hiện tại không nguyên tố thì dừng" đúng với định nghĩa số siêu nguyên tố.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Số siêu nguyên tố là một loại 'Prime Prefix' (tiền tố nguyên tố). Nếu ta xây dựng số từ trái sang phải, mỗi tiền tố của nó đều phải là số nguyên tố.
• Chữ số đầu tiên của một số siêu nguyên tố phải là một trong các số nguyên tố 1 chữ số: 2, 3, 5, 7.
• Chữ số tiếp theo của một số siêu nguyên tố (sau chữ số đầu tiên) chỉ có thể là 1, 3, 7, 9. Điều này loại bỏ rất nhiều khả năng.
• Vì N nhỏ (≤ 10), các thuật toán quay lui (Backtracking) có độ phức tạp chấp nhận được (khoảng 3^9 ≈ 19,000 số) là đủ để giải quyết bài toán một cách nhanh chóng.

Lỗi thường gặp

• Quên kiểm tra tính nguyên tố của các tiền tố ở giữa (ví dụ: chỉ kiểm tra số cuối cùng). Phải đảm bảo rằng mọi tiền tố (từ 1 đến n chữ số) đều là số nguyên tố.
• Xử lý sai trường hợp n=1. Cần trả về 2, 3, 5, 7.
• Thử các chữ số không cần thiết (ví dụ thêm 2, 4, 5, 6, 8 vào các số đang xây dựng). Dù có thể loại bỏ bằng hàm isPrime, việc hạn chế các lựa chọn chữ số trong vòng lặp quay lui sẽ cải thiện hiệu năng.
• Lỗi biến toàn cục trong đệ quy: Solution 1 sử dụng biến x toàn cục để lưu giá trị hiện tại và khôi phục lại (backtracking) sau khi đệ quy. Nếu không khôi phục đúng, kết quả sẽ sai.