Truy vấn in tất cả ước số của n bằng C++ (Sàng Eratosthenes)

Cho số nguyên n, in ra tất cả ước số của nó. Ví dụ:

Input: 15 Output: 1 3 5 15 Input: 30 Output: 1 2 3 5 6 10 15 30

Áp dụng ý tưởng của Sàng Eratosthenes để tiền tính ước số cho mọi số đến giới hạn lớn.

Cách tiếp cận

Duyệt i từ 1 đến MAX, với mỗi i thêm vào danh sách ước của các bội số j = i, 2i, 3i.... Khi có truy vấn, chỉ cần in danh sách đã tính sẵn.

Ví dụ

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

vector<int> divisors[100001];

void findsieve(int max) {
    for(int i = 1; i <= max; i++) {
        for(int j = i; j <= max; j += i)
            divisors[j].push_back(i);
    }
}

void __print(int n) {
    for(auto x : divisors[n]) cout << x << " ";
    cout << "\n";
}

int main() {
    findsieve(100000);
    int n = 6;
    __print(n);
    n = 30;
    __print(n);
    return 0;
}

Kết quả

1 2 3 6 1 2 3 5 6 10 15 30

Giải thích

Tiền xử lý O(N log N) (tương tự sàng). Mỗi truy vấn in ước số trong O(số ước). Phù hợp khi có nhiều truy vấn (Q lớn).

Kết luận

Đã giải quyết bài toán in ước số của n cho nhiều truy vấn bằng kỹ thuật tiền xử lý dạng Sàng Eratosthenes. Code C++ mẫu, dễ chuyển sang ngôn ngữ khác.