求因数

1.暴力枚举法

一般来说，因数分解常用方法为暴力枚举，其时间复杂度为$O(\sqrt{n}$)

vector<int> factor(int n) {
    vector<int> factors;
    for (int i = 1; i * i <= n; i++) {
       if(n%i==0){
            if(n/i!=i){
                factors.push_back(i);
                factors.push_back(n/i);
            }
            else factors.push_back(i);
       }
    }
    return factors;
}

这种方法代码简单，无需预处理，适用于少量查询，但当需要查询的数字过多，暴力法则变得不那么优秀，需引入其他更优解

2.预计算所有数的因数表

时间复杂度$O(nlog{n})$，单次查询$O(1)$

vector<int>factors[N];
void factor(){
    for(int i=1e6;i>=1;i--){
        for(int j=i;j<=1e6;j+=i){
            factors[j].push_back(i);
        }
    }
}

3.SPF 线性筛

核心思路：

1. 使用 SPF（Smallest Prime Factor）线性筛，预计算 spf[i]（最小质因子）。
2. 使用 SPF 快速分解 n 的质因子，时间复杂度 O(log n)。
3. 枚举所有可能的因数，利用回溯法生成所有因数，时间复杂度 O(d)（d 为因数个数，通常远小于 n）。

时间复杂度分析：

1. 预处理 SPF 线性筛：O(n)（一次性计算）。

2. 单次查询

   • 因数分解：O(log n)（因为 spf[n] 查询次数至多 log n）。
   • 生成所有因数：O(d)，其中 d 是因数个数，通常 $d = O(n^{1/3})$。

#include <iostream>
#include <vector>
#include <set>

using namespace std;

const int MAXN = 1000000; // 预处理范围
vector<int> spf(MAXN + 1); // 存储最小质因子

// **线性筛** 预计算 SPF
void sieve_spf(int N) {
    for (int i = 1; i <= N; i++) spf[i] = i;  // 先设为自身
    for (int i = 2; i <= N; i++) {
        if (spf[i] == i) {  // i 是质数
            for (int j = i * 2; j <= N; j += i) {
                if (spf[j] == j) spf[j] = i; // 记录最小质因子
            }
        }
    }
}

// **用 SPF 进行因数分解**
vector<pair<int, int>> factorize(int n) {
    vector<pair<int, int>> factors; // 记录 (质因子, 指数)
    while (n > 1) {
        int prime = spf[n], count = 0;
        while (n % prime == 0) {
            n /= prime;
            count++;
        }
        factors.push_back({prime, count});
    }
    return factors;
}

// **基于质因子分解，枚举所有因数**
void generate_divisors(int index, int current, vector<pair<int, int>>& factors, vector<int>& divisors) {
    if (index == factors.size()) {
        divisors.push_back(current);
        return;
    }
    int prime = factors[index].first, exponent = factors[index].second;
    for (int i = 0; i <= exponent; i++) {
        generate_divisors(index + 1, current, factors, divisors);
        current *= prime;
    }
}

// **查询 n 的所有因数**
vector<int> get_divisors(int n) {
    vector<pair<int, int>> factors = factorize(n); // O(log n) 分解
    vector<int> divisors;
    generate_divisors(0, 1, factors, divisors); // O(d) 生成因数
    sort(divisors.begin(), divisors.end()); // 让因数按顺序输出
    return divisors;
}

int main() {
    sieve_spf(MAXN); // 预计算最小质因子

    int num;
    cout << "输入要查询的数: ";
    cin >> num;

    if (num <= 0 || num > MAXN) {
        cout << "数值超出范围!\n";
        return 1;
    }

    vector<int> divisors = get_divisors(num);
    cout << "所有因数: ";
    for (int d : divisors) {
        cout << d << " ";
    }
    cout << endl;

    return 0;
}

总结