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 thành tích các thừa số nguyên tố và in ra theo thứ tự tăng dần, cách nhau bởi dấu ''. Ví dụ: n = 90 thì kết quả là 2335. Dữ liệu đầu vào n nằm trong khoảng 2 ≤ n ≤ 10^6.

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

Cách Brute Force (Tìm ước số)

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

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

int main() {
    int a;
    cin >> a;
    if (a == 1) cout << 1;
    else if (a == 0) cout << 0;
    else
    for (int i = 2; i <= a; i++) {
        if (isPrime(i) && a % i == 0) {
            cout << i;
            a /= i;
            if (a == 1) break;
            cout << '*';
            i = 1;
        }
    }
    return 0;
}

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

Cách tiếp cận này sử dụng vòng lặp từ 2 đến n (biến i). Với mỗi i, nó kiểm tra xem i có phải là số nguyên tố hay không bằng hàm isPrime. Nếu i là số nguyên tố và chia hết cho a (giá trị hiện tại của n), nó in ra i, chia a cho i và gán i = 1 để lặp lại từ đầu. Phương pháp này khá chậm và không hiệu quả do lặp lại quá nhiều lần và kiểm tra tính nguyên tố không cần thiết.

Cách Trial Division (Phân tích bằng cách thử chia)

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

int main(){
    int n;
    cin>>n;
    int i = 2;
    while (n > 1)
    {
        while (n % i == 0 && n > 1)
            {
                if (n / i == 1) cout << i;
                    else cout <<i <<'*';
                n/=i;
            }
        i++;
    }
}

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

Cách tiếp cận này chia n cho các số i tăng dần từ 2. Với mỗi i, nó lặp lại việc chia n cho i khi n còn chia hết. Cứ mỗi lần chia, nó in ra i. Khi i không còn chia hết nữa, nó tăng i lên 1. Vòng lặp dừng khi n giảm xuống bằng 1. Phương pháp này hoạt động tốt nhưng có thể tối ưu hơn nếu chỉ kiểm tra các số lẻ sau khi đã xử lý hết các thừa số 2.

Cách Optimized Trial Division (Tối ưu hóa)

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

int main() {
    long long n;
    cin >> n;

    bool first = true;

    // Phân tích các thừa số 2
    while (n % 2 == 0) {
        if (!first) cout << '*';
        cout << 2;
        first = false;
        n /= 2;
    }

    // Phân tích các thừa số lẻ
    for (long long i = 3; i * i <= n; i += 2) {
        while (n % i == 0) {
            if (!first) cout << '*';
            cout << i;
            first = false;
            n /= i;
        }
    }

    // Nếu còn lại 1 số nguyên tố lớn hơn 1
    if (n > 1) {
        if (!first) cout << '*';
        cout << n;
    }

    return 0;
}

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

Đây là phương pháp tối ưu nhất. Đầu tiên, nó chia n cho 2 hết mức có thể (xử lý riêng các thừa số chẵn). Sau đó, nó chỉ duyệt các số lẻ từ 3 đến căn bậc hai của n (sqrt(n)). Cứ mỗi số i lẻ, nó chia hết n cho i bao nhiêu lần thì in i ra bấy nhiêu lần. Cuối cùng, nếu sau vòng lặp n vẫn lớn hơn 1, tức là n còn lại là một số nguyên tố (vượt quá giới hạn sqrt(n) ban đầu), nó in ra n.

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

Bài học kinh nghiệm

• Việc chỉ duyệt đến căn bậc hai của n (i * i <= n) vì một số n chỉ có thể có ước nguyên tố lớn hơn sqrt(n) khi đó là số nguyên tố.
• Xử lý thừa số 2 riêng giúp giảm một nửa số lần lặp (chỉ cần lặp các số lẻ từ 3 trở đi).

Lỗi thường gặp

• Định dạng in sai: In thừa dấu '' ở cuối hoặc thiếu dấu '' ở giữa các số.
• Sử dụng biến số nguyên nhỏ (int) cho n lớn (lên tới 10^6) có thể gây tràn số nếu nhân đôi bên trong vòng lặp (dù 10^6 vẫn nằm trong giới hạn int, nhưng dùng long long là an toàn hơn).