Hiểu bài toán

Bài toán yêu cầu phân tích một số nguyên dương n (1 ≤ n ≤ 10^12) thành thừa số nguyên tố. Điều đó có nghĩa là cần tìm các số nguyên tố pi và số mũ tương ứng αi sao cho n = p1^{α1} × p2^{α2} × ... × pk^{αk}. Các pi phải là số nguyên tố phân biệt và được sắp xếp tăng dần. Output gồm số lượng cặp (pi, α_i) và các cặp này.

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

Cách Brute Force (Tìm ước số nguyên tố trực tiếp)

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

int main() {
    long long n;
    scanf("%lld", &n);
    long long a[100], b[100];
    int x = 0;

    // Thử chia n cho tất cả các số từ 2 trở lên
    for (long long i = 2; i <= n; i++) {
        if (n % i == 0) {
            a[x] = i;
            b[x] = 0;
            while (n % i == 0) {
                b[x]++;
                n /= i;
            }
            x++;
        }
    }

    printf("%d\n", x);
    for (int i = 0; i < x; i++) {
        printf("%lld %lld\n", a[i], b[i]);
    }

    return 0;
}

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

Phương pháp này thử chia n cho các số i bắt đầu từ 2. Nếu n chia hết cho i, thì i là một thừa số nguyên tố (hoặc bội của thừa số nguyên tố). Trong khi n chia hết cho i, ta chia n cho i và tăng số mũ. Vòng lặp chạy cho đến khi n giảm xuống bằng 1.

Tuy nhiên, với n lên tới 10^12, độ phức tạp O(n) là quá lớn và chắc chắn sẽ gây ra Time Limit Exceeded. Phương pháp này chỉ hiệu quả với n rất nhỏ.

Cách Optimized Trial Division (Chia hết đến căn bậc hai)

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

int main() {
    long long n;
    scanf("%lld", &n);
    long long tmp = n;
    long long a[100], b[100];
    int x = 0;

    // Phân tích thừa số nguyên tố
    // Chỉ cần thử chia đến căn bậc hai của n
    for (long long i = 2; i * i <= tmp; i++) {
        if (n % i == 0) {
            a[x] = i;
            b[x] = 0;
            while (n % i == 0) {
                b[x]++;
                n /= i;
            }
            x++;
        }
    }

    // Nếu sau khi chia vẫn còn số > 1 thì đó là 1 thừa số nguyên tố
    if (n > 1) {
        a[x] = n;
        b[x] = 1;
        x++;
    }

    // In kết quả
    printf("%d\n", x);
    for (int i = 0; i < x; i++) {
        printf("%lld %lld\n", a[i], b[i]);
    }

    return 0;
}

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

Đây là cách tiếp cận chuẩn để phân tích thừa số nguyên tố cho n trong khoảng 10^12.

1. Vòng lặp chính (i từ 2 đến √n): Ta chỉ cần thử chia n cho các số i cho đến i*i > n. Nếu n có ước khác 1 và chính nó, thì ước đó phải nhỏ hơn hoặc bằng √n. Nếu sau vòng lặp này n vẫn lớn hơn 1, thì n còn lại chính là một số nguyên tố lớn hơn √n ban đầu.
2. Xử lý số mũ: Khi tìm thấy i chia hết n, ta lặp lại việc chia n cho i cho đến khi không còn chia hết để đếm số mũ.
3. Kiểm tra n còn lại: Sau vòng lặp, nếu n > 1, thì n đó là một thừa số nguyên tố (vì nó không chia hết cho bất kỳ số nào từ 2 đến √n ban đầu).

Độ phức tạp O(√n) ≈ 10^6 thao tác, hoàn toàn chấp nhận được trong thời gian chạy thông thường.

Cách Optimized Trial Division (Cải tiến)

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

void phanTichThuaSoNguyenTo(long long n) {
    long long p[20];
    int alpha[20];
    int k = 0;

    // Xử lý thừa số 2 riêng biệt
    if (n % 2 == 0) {
        p[k] = 2;
        int count = 0;
        while (n % 2 == 0) {
            count++;
            n /= 2;
        }
        alpha[k] = count;
        k++;
    }

    // Xử lý các số lẻ từ 3 đến √n
    for (long long i = 3; i * i <= n; i += 2) {
        if (n % i == 0) {
            p[k] = i;
            int count = 0;
            while (n % i == 0) {
                count++;
                n /= i;
            }
            alpha[k] = count;
            k++;
        }
    }

    // Xử lý thừa số nguyên tố còn lại
    if (n > 1) {
        p[k] = n;
        alpha[k] = 1;
        k++;
    }

    printf("%d\n", k);
    for (int i = 0; i < k; i++) {
        printf("%lld %d\n", p[i], alpha[i]);
    }
}

int main() {
    long long n;
    scanf("%lld", &n);
    phanTichThuaSoNguyenTo(n);
    return 0;
}

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

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

1. Tách riêng số 2: Số 2 là số nguyên tố chẵn duy nhất. Việc chia hết cho 2 được xử lý trước bằng một vòng lặp riêng. Sau đó, ta chỉ cần xét các số lẻ.
2. Bước nhảy 2: Trong vòng lặp kiểm tra các số lẻ, ta tăng i lên 2 (i += 2) sau mỗi lần lặp (3, 5, 7, ...). Điều này giảm một nửa số lần lặp so với việc tăng 1 đơn vị.
3. Logic tương tự: Phần còn lại giữ nguyên logic: chỉ kiểm tra đến √n và xử lý phần còn lại của n.

Phương pháp này có độ phức tạp tương tự O(√n) nhưng thực tế chạy nhanh hơn một chút do giảm số lần lặp.

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

Bài học kinh nghiệm

• Một số n chỉ có thể chứa các thừa số nguyên tố nhỏ hơn hoặc bằng √n, hoặc chính nó là một số nguyên tố.
• Việc loại bỏ các thừa số ngay khi tìm thấy giúp giảm giá trị của n nhanh chóng, từ đó giảm thời gian kiểm tra các số tiếp theo.
• Nếu n có giá trị lớn sau khi đã chia hết cho các số i đến √n ban đầu, thì n còn lại chắc chắn là một số nguyên tố.

Lỗi thường gặp

• Sử dụng kiểu dữ liệu int để lưu n (n ≤ 10^12) gây tràn số. Phải dùng long long.
• Quên kiểm tra trường hợp n > 1 sau vòng lặp. Nếu n ban đầu là một số nguyên tố lớn (ví dụ: 999999999989), vòng lặp sẽ không tìm thấy ước nào và cần in ra n còn lại.
• Lặp sai điều kiện dừng (ví dụ: i <= sqrt(n) nhưng không tính toán sqrt() chính xác, hoặc i++ thay vì i+=2 trong phiên bản tối ưu).