生成一个数的所有因数分解

Question

我想找到 [1,10⁷] 范围内的所有数字除数。我知道它可以在 O(sqrt(n)) 中解决。但在此之前必须运行筛选 Eratosthenes 可以很容易地修改以获得数字的质因数分解（通过跟踪每个数字的质因数之一）。所以我想知道使用素数分解生成所有因子会更有效吗？
设 n = p₁^k₁ * p₂ ^k₂*....*p_m^k_m

我觉得这个记法经过筛后O(m+Σk_i)就可以得到
经过一番思考，我想出了以下代码来生成因子：

int factors[]={2,5};        // array containing all the factors
int exponents[]={2,2};      // array containing all the exponents of factors
                            // exponents[i] = exponent of factors[i]
vector <int> ans;           // vector to hold all possible factors

/*
*   stores all possible factors in vector 'ans'
*   using factors and exponents from index l to r(both inclusive)
*/
void gen(int factors[],int exponents[],vector<int>& ans,int l,int r)
{
    if(l==r)                        
    {
        int temp = 1;
        for(int i=0;i<=exponents[l];i++)
        {
            ans.push_back(temp);
            temp *= factors[l];
        }
        return;
    }
    gen(factors,exponents,ans,l+1,r);
    int temp=factors[l];
    int size = ans.size();
    for(int i=1;i<=exponents[l];i++)
    {
        for(int j=0;j<size;j++)
        {
            ans.push_back(ans[j]*temp);
        }
        temp *= factors[l];
    }
}

我认为它的时间复杂度至少是Ω(没有因素) = Ω(∠(1+k_i)).

所以我的问题是：
1) 以这种方式生成因子是否比通常（O(sqrt(n)) 循环方法）更快？
2）上面给出的代码可以优化吗？

Answer 1

第一个最明显的优化是预分配答案向量。你确切地知道会有多少个因素（因为你已经给出了公式 ‖(1+k_i) ).

如果您自己管理堆栈而不是使用递归，您将获得最佳解决方案（每个因素只需要 1 次查找和 1 次乘法）。

是这样的吗？

int factors_count = 1;
for (int i = 0; i < r; ++i)
{
    factors_count *= 1+exponents[i];
}
ans.resize(factors_count);
ans[0] = 1;
int count = 1;
for (int stack_level = 0; stack_level < r; ++stack_level)
{
    const int count_so_far = count;
    const int prime = factors[stack_level];
    const int exponent = exponents[stack_level];
    int multiplier = 1;
    for (int j = 0; j < exponent; ++j)
    {
        multiplier *= prime;
        for (int i = 0; i < count_so_far; ++i)
        {
            ans[count++] = ans[i] * multiplier;
        }
    }
}

我什至没有尝试编译它，所以买者自负。

生成一个数的所有因数分解

Generating all divisors of a number given its prime factorization

c

c++

algorithm

primes

factorization