Phân tích thừa số nguyên tố dùng Sieve O(log n) cho nhiều truy vấn C++

Giới thiệu

Phân tích thừa số nguyên tố (Prime Factorization) cho nhiều truy vấn. Sử dụng Sieve of Eratosthenes tiền xử lý để tìm ước nguyên tố nhỏ nhất (Smallest Prime Factor - SPF) cho mọi số ≤ N, sau đó phân tích mỗi số trong O(log n).

Ý tưởng cốt lõi

1. Tiền tính mảng spf[x] = ước nguyên tố nhỏ nhất của x (cho mọi x ≤ MAX)
2. Phân tích n: lặp lấy spf[n], n /= spf[n] cho đến khi n = 1

Mã nguồn hoàn chỉnh

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

const int MAXN = 1000001;
int spf[MAXN]; // Smallest Prime Factor

void sieve() {
    for (int i = 0; i < MAXN; i++) spf[i] = i;
    spf[0] = spf[1] = 1;
    
    for (int i = 2; i * i < MAXN; i++) {
        if (spf[i] == i) { // i là số nguyên tố
            for (int j = i * i; j < MAXN; j += i) {
                if (spf[j] == j) spf[j] = i; // Chỉ gán lần đầu (nhỏ nhất)
            }
        }
    }
}

vector getPrimeFactors(int n) {
    vector factors;
    while (n != 1) {
        factors.push_back(spf[n]);
        n /= spf[n];
    }
    return factors;
}

int main() {
    sieve();
    
    int queries[] = {45214, 100, 9973, 1000000};
    for (int n : queries) {
        vector factors = getPrimeFactors(n);
        cout << n << " = ";
        for (int i = 0; i < factors.size(); i++) {
            cout << factors[i] << (i+1 < factors.size() ? " x " : "");
        }
        cout << endl;
    }
    return 0;
}

Kết quả chạy chương trình

45214 = 2 x 13 x 37 x 47
100 = 2 x 2 x 5 x 5
9973 = 9973
1000000 = 2 x 2 x 2 x 2 x 2 x 2 x 5 x 5 x 5 x 5 x 5 x 5

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

So sánh phương pháp

Ứng dụng thực tế

• Tính số ước, tổng ước, hàm Euler φ(n)
• RSA cryptography (phân tích modulus)
• Bài toán số học thi đấu (Codeforces, Spoj)

Kết luận

Sieve SPF là kỹ thuật chuẩn cho phân tích thừa số nguyên tố nhiều truy vấn. Tiền xử lý một lần, trả lời mỗi query cực nhanh O(log n).