Hiểu bài toán

Bài toán yêu cầu đếm số lượng ước nguyên tố khác nhau của một số nguyên dương N. Ví dụ, với N = 12 = 2^2 * 3, số ước nguyên tố là 2 và 3, kết quả là 2. N có thể lớn (sử dụng kiểu long long), nên cần thuật toán hiệu quả để phân tích N thành thừa số nguyên tố.

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

Cách Brute Force (Tìm ước và Kiểm tra)

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

bool snt(long long x){
    if(x < 2) return false;
    if(x == 2 || x == 3) return true;
    if(x % 2 == 0 || x % 3 == 0) return false;
    for(long long i = 5; i * i <= x; i += 6)
        if(x % i == 0 || x % (i + 2) == 0)
            return false;
    return true;
}

int main(){
    long long n;
    cin >> n;
    long long dem = 0;
    for(long long i = 2; i * i <= n; i++){
        if(n % i == 0){
            if(snt(i)) dem++;
            while(n % i == 0)
                n /= i;
        }
    }
    if(n > 1) dem++;
    cout << dem;
}

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

Thuật toán này duyệt qua các số i từ 2 đến sqrt(N). Nếu i là ước của N, nó kiểm tra xem i có phải là số nguyên tố bằng hàm snt. Hàm snt sử dụng vòng lặp đến sqrt(i). Trong trường hợp xấu nhất (ví dụ N là số nguyên tố lớn), độ phức tạp tổng thể gần như O(N) vì ta phải duyệt nhiều số và kiểm tra tính nguyên tố cho mỗi số.

Cách Phân tích thừa số nguyên tố (Prime Factorization)

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

int main() {
    long long n;
    cin >> n;
    long long a = 0;
    long long i = 2;
    while(i * i <= n){
        bool t = false;
        while(n % i == 0){
            t = true;
            n /= i;
        }
        if(t) a++;
        i++;
    }
    if(n > 1) a++;
    cout << a;
}

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

Đây là cách tiếp cận chuẩn để phân tích một số thành thừa số nguyên tố. Ta chỉ cần duyệt i từ 2 đến sqrt(N). Nếu i là ước của N, ta chia hết N cho i cho đến khi không chia hết được nữa. Vì ta chỉ quan tâm đến số lượng ước nguyên tố khác nhau, ta chỉ cần đánh dấu rằng i là một ước (không cần quan tâm số mũ). Nếu sau vòng lặp mà N > 1, thì N còn lại là một số nguyên tố (ước nguyên tố cuối cùng).

Cách Tối ưu với số lẻ (Optimized Trial Division)

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

int main() {
    long long n;
    cin >> n;
    long long dem = 0;

    // Xử lý ước 2 riêng
    if (n % 2 == 0) {
        dem++;
        while (n % 2 == 0) n /= 2;
    }

    // Chỉ duyệt các số lẻ từ 3
    for (long long i = 3; i * i <= n; i += 2) {
        if (n % i == 0) {
            dem++;
            while (n % i == 0) n /= i;
        }
    }

    if (n > 1) dem++;
    cout << dem;
}

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

Đây là phiên bản tối ưu của Approach 2. Nó xử lý số chẵn (ước 2) riêng để có thể tăng số i lên 2 đơn vị mỗi bước (chỉ kiểm tra các số lẻ). Điều này giảm một nửa số lần lặp so với việc kiểm tra tất cả các số tự nhiên. Logic vẫn là phân tích thừa số nguyên tố, nhưng chạy nhanh hơn trong thực tế.

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

Bài học kinh nghiệm

• Bài toán yêu cầu số lượng ước nguyên tố khác nhau, không phải tổng số ước hay số mũ của chúng.
• Phân tích N thành thừa số nguyên tố (Prime Factorization) là chìa khóa.
• Tốc độ chạy của thuật toán phụ thuộc vào vòng lặp for (i = 2; i * i <= n; i++). Nếu n lớn và là số nguyên tố, vòng lặp này chạy đến sqrt(n).
• Việc kiểm tra tính nguyên tố của i (như trong Solution 1) là không cần thiết và gây chậm máy vì ta đã biết rằng nếu i chia hết n và n đang bị chia hết các thừa số nhỏ hơn trước đó, thì i chắc chắn là số nguyên tố.

Lỗi thường gặp

• Sử dụng biến số nguyên nhỏ (như int) cho n hoặc biến vòng lặp i, dẫn đến tràn số (overflow) khi i * i vượt quá giới hạn của int nếu n lớn (dù n trong đề là long long, thói quen dùng int vẫn hay gây lỗi).
• Quên kiểm tra số còn lại sau vòng lặp (if (n > 1)). Nếu n ban đầu là số nguyên tố lớn (ví dụ 10^9 + 7), vòng lặp kết thúc với n > 1 và đó là ước nguyên tố cần đếm.
• Vòng lặp while(n % i == 0) là bắt buộc để loại bỏ hết các thừa số i trước khi sang i tiếp theo, đảm bảo mỗi ước nguyên tố chỉ được đếm 1 lần.