Editorial for ptit057: Số siêu nguyên tố

Hiểu bài toán

Bài toán yêu cầu tìm tất cả các 'số siêu nguyên tố' nhỏ hơn hoặc bằng N (1 ≤ N ≤ 30000). Một số được gọi là số siêu nguyên tố nếu nó là số nguyên tố và khi loại bỏ lần lượt các chữ số từ phải sang trái, các số còn lại vẫn là số nguyên tố. Ví dụ: 233 là số nguyên tố, 23 là số nguyên tố, 2 là số nguyên tố nên 233 là số siêu nguyên tố. Chúng ta cần in ra các số này theo thứ tự tăng dần hoặc in -1 nếu không có.

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

Cách Brute Force với kiểm tra đệ quy

#include <stdio.h>
#include <math.h>

// Hàm kiểm tra số nguyên tố
int is_prime(int n) {
    if (n < 2) return 0;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return 0;
    }
    return 1;
}

// Hàm kiểm tra số siêu nguyên tố
int is_super_prime(int n) {
    while (n > 0) {
        if (!is_prime(n)) return 0;
        n /= 10;
    }
    return 1;
}

int main() {
    int n;
    scanf("%d", &n);
    int found = 0;
    for (int i = 2; i <= n; i++) {
        if (is_super_prime(i)) {
            printf("%d ", i);
            found = 1;
        }
    }
    if (!found) printf("-1");
    return 0;
}

• Time Complexity: O(N * sqrt(N) * log N)
• Space Complexity: O(1)

Phương pháp này kiểm tra từng số từ 2 đến N. Với mỗi số, đầu tiên kiểm tra xem nó có phải là số nguyên tố không. Nếu là số nguyên tố, tiếp tục chia cho 10 để kiểm tra các tiền tố của nó. Ví dụ với 233: kiểm tra 233 → 23 → 2. Độ phức tạp: Vòng lặp chính chạy N lần. Mỗi lần kiểm tra số nguyên tố mất O(sqrt(i)). Việc kiểm tra các tiền tố mất O(log i) lần gọi is_prime. Tổng thể O(N * sqrt(N) * log N). Với N=30000, thời gian chạy hoàn toàn chấp nhận được.

Cách Tạo trước các số siêu nguyên tố

#include <stdio.h>
#include <math.h>
#include <stdbool.h>

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

// Sinh các số siêu nguyên tố bằng BFS
void generate_super_primes(int limit) {
    int queue[10000];
    int front = 0, rear = 0;

    // Khởi tạo với các chữ số đơn vị là số nguyên tố
    int seeds[] = {2, 3, 5, 7};
    for (int i = 0; i < 4; i++) {
        if (seeds[i] <= limit) {
            queue[rear++] = seeds[i];
            printf("%d ", seeds[i]);
        }
    }

    while (front < rear) {
        int current = queue[front++];
        for (int digit = 1; digit <= 9; digit++) {
            int next = current * 10 + digit;
            if (next > limit) continue;
            if (is_prime(next)) {
                queue[rear++] = next;
                printf("%d ", next);
            }
        }
    }
}

int main() {
    int n;
    scanf("%d", &n);
    if (n < 2) {
        printf("-1");
        return 0;
    }
    generate_super_primes(n);
    return 0;
}

• Time Complexity: O(S) where S is number of super primes ≤ N (very small, ~O(log N))
• Space Complexity: O(S)

Thay vì kiểm tra tất cả các số, phương pháp này chỉ sinh ra các số có thể là siêu nguyên tố. Bắt đầu từ các chữ số đơn vị nguyên tố (2,3,5,7), ta liên tục thêm các chữ số từ 1-9 vào bên phải nếu số mới tạo ra vẫn là số nguyên tố. Ví dụ: 2 → 23, 29 (vì 21, 22, 24-28, 20 không nguyên tố). Cách này rất hiệu quả vì số lượng số siêu nguyên tố rất ít (chỉ 83 số ≤ 30000).

Cách Tối ưu hóa với kiểm tra nhanh

#include <stdio.h>
#include <math.h>
#include <stdbool.h>

// Mảng đánh dấu số nguyên tố (sàng Eratosthenes)
bool prime[30001];

void sieve(int n) {
    for (int i = 2; i <= n; i++) prime[i] = true;
    for (int i = 2; i * i <= n; i++) {
        if (prime[i]) {
            for (int j = i * i; j <= n; j += i) {
                prime[j] = false;
            }
        }
    }
}

int is_super_prime(int n) {
    while (n > 0) {
        if (!prime[n]) return 0;
        n /= 10;
    }
    return 1;
}

int main() {
    int n;
    scanf("%d", &n);
    sieve(n);

    int found = 0;
    for (int i = 2; i <= n; i++) {
        if (is_super_prime(i)) {
            printf("%d ", i);
            found = 1;
        }
    }
    if (!found) printf("-1");
    return 0;
}

• Time Complexity: O(N log log N) ~ O(N)
• Space Complexity: O(N)

Sử dụng sàng Eratosthenes để tạo mảng đánh dấu số nguyên tố O(N log log N). Sau đó chỉ cần duyệt từ 2 đến N, kiểm tra từng số bằng cách xem trong mảng đã đánh dấu. Việc kiểm tra các tiền tố cũng chỉ cần O(log N) thời gian tra cứu mảng. Đây là cách hiệu quả nhất cho N=30000 vì chi phí sàng rất nhỏ và tra cứu O(1).

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

Bài học kinh nghiệm

• Số siêu nguyên tố có tính chất đệ quy: một số là siêu nguyên tố nếu nó là nguyên tố và hậu tố (bỏ chữ số đầu) cũng là siêu nguyên tố
• Chữ số đầu tiên của số siêu nguyên tố phải là 2, 3, 5, hoặc 7 (các số nguyên tố 1 chữ số)
• Với N nhỏ (≤30000), phương pháp sàng Eratosthenes kết hợp kiểm tra đơn giản là hiệu quả nhất
• Số lượng siêu nguyên tố tăng rất chậm, có thể tối ưu bằng cách sinh ra chúng thay vì kiểm tra tất cả

Lỗi thường gặp

• Quên kiểm tra số < 2 không phải nguyên tố
• In -1 khi không tìm thấy số nào
• Xử lý số 0 sai trong vòng lặp while(n) khi n=0
• In thừa dấu cách cuối cùng (cần kiểm tra format output)