Editorial for ptit056: Số đặc biệt 2

Hiểu bài toán

Bài toán yêu cầu kiểm tra xem một số nguyên dương n có phải là 'số đặc biệt' hay không. Một số được gọi là đặc biệt nếu nó thỏa mãn hai điều kiện: (1) n là số nguyên tố và (2) tổng các chữ số của n cũng là một số nguyên tố. Dữ liệu đầu vào là số n trong khoảng từ 1 đến 100.000. Đầu ra là 'YES' nếu n là số đặc biệt, ngược lại là 'NO'.

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

Cách Phương pháp kiểm tra nguyên tố cơ bản

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

int isPrime(int n) {
    if (n <= 1) return 0;
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) return 0;
    }
    return 1;
}

int sumDigits(int n) {
    int sum = 0;
    while (n > 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}

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

    if (isPrime(n)) {
        int digitSum = sumDigits(n);
        if (isPrime(digitSum)) {
            printf("YES");
        } else {
            printf("NO");
        }
    } else {
        printf("NO");
    }

    return 0;
}

• Time Complexity: O(sqrt(n))
• Space Complexity: O(1)

Đây là cách tiếp cận trực tiếp nhất. Hàm isPrime kiểm tra tính nguyên tố của n bằng cách lặp từ 2 đến căn bậc hai của n. Hàm sumDigits tính tổng các chữ số của n. Trong hàm chính, ta kiểm tra n có phải là số nguyên tố không. Nếu có, ta tính tổng chữ số và kiểm tra xem tổng đó có phải là số nguyên tố không. Nếu cả hai điều kiện đều đúng, in ra 'YES', ngược lại in 'NO'.

Cách Tối ưu hóa kiểm tra nguyên tố

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

int nt(int n) {
    if (n < 2) return 0;
    if (n == 2) return 1;
    if (n % 2 == 0) return 0;
    for (int i = 3; i <= sqrt(n); i += 2) {
        if (n % i == 0) return 0;
    }
    return 1;
}

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

    // Kiểm tra n là số nguyên tố
    if (!nt(n)) {
        printf("NO");
        return 0;
    }

    // Tính tổng chữ số
    int sum = 0;
    int temp = n;
    while (temp > 0) {
        sum += temp % 10;
        temp /= 10;
    }

    // Kiểm tra tổng chữ số là số nguyên tố
    if (nt(sum)) {
        printf("YES");
    } else {
        printf("NO");
    }

    return 0;
}

• Time Complexity: O(sqrt(n))
• Space Complexity: O(1)

Phương pháp này tương tự như cách đầu tiên nhưng tối ưu hóa hàm kiểm tra nguyên tố bằng cách loại bỏ các số chẵn (trừ 2) khỏi vòng lặp. Điều này giảm một nửa số lần lặp, giúp tăng tốc độ chạy một chút. Logic kiểm tra hai điều kiện vẫn được giữ nguyên.

Cách Sử dụng mảng đánh dấu (Sieve) cho tổng chữ số

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

#define MAX_SUM 45 // 99999 có tổng chữ số lớn nhất là 45

// Mảng đánh dấu các số nguyên tố
bool isPrimeSum[MAX_SUM + 1];

void sieve() {
    for (int i = 0; i <= MAX_SUM; i++) isPrimeSum[i] = true;
    isPrimeSum[0] = isPrimeSum[1] = false;
    for (int i = 2; i * i <= MAX_SUM; i++) {
        if (isPrimeSum[i]) {
            for (int j = i * i; j <= MAX_SUM; j += i) {
                isPrimeSum[j] = false;
            }
        }
    }
}

int isPrime(int n) {
    if (n < 2) return 0;
    if (n == 2) return 1;
    if (n % 2 == 0) return 0;
    for (int i = 3; i <= sqrt(n); i += 2) {
        if (n % i == 0) return 0;
    }
    return 1;
}

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

    sieve();

    // Tính tổng chữ số
    int sum = 0;
    int temp = n;
    while (temp > 0) {
        sum += temp % 10;
        temp /= 10;
    }

    // Kiểm tra cả hai điều kiện
    if (isPrime(n) && isPrimeSum[sum]) {
        printf("YES");
    } else {
        printf("NO");
    }

    return 0;
}

• Time Complexity: O(sqrt(n))
• Space Complexity: O(1)

Phương pháp này kết hợp Sieve of Eratosthenes để kiểm tra tính nguyên tố của tổng chữ số. Vì tổng chữ số của n (với n <= 100,000) không vượt quá 45, ta có thể预先 tính toán và lưu trữ các số nguyên tố trong khoảng này. Điều này giúp việc kiểm tra tính nguyên tố của tổng chữ số trở thành thao tác O(1). Tuy nhiên, với giới hạn bài toán nhỏ, sự cải thiện này không đáng kể so với chi phí setup Sieve.

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

Bài học kinh nghiệm

• Bài toán có hai phần độc lập: kiểm tra n có phải số nguyên tố và kiểm tra tổng chữ số của n có phải số nguyên tố.
• Tổng chữ số của một số <= 100,000 luôn nhỏ hơn hoặc bằng 45 (từ số 99999), nên ta có thể tối ưu việc kiểm tra tính nguyên tố cho tổng chữ số.
• Độ phức tạp thuật toán kiểm tra nguyên tố cơ bản O(sqrt(n)) là hoàn toàn đủ hiệu năng cho n <= 100,000.

Lỗi thường gặp

• Quên kiểm tra trường hợp n <= 1 (không phải số nguyên tố).
• Sai logic trong hàm tính tổng chữ số (ví dụ: không xử lý đúng số 0).
• Kiểm tra điều kiện sai thứ tự (ví dụ: kiểm tra tổng chữ số trước khi kiểm tra n có phải số nguyên tố).