基於因子分解生成數字的所有因數

Question

我想查找範圍內的所有數字因子[1,10 ]。我知道它可以在O（sqrt（n））中解決。但在此之前必須運行Eratosthenes的篩選，通過跟蹤每個數字的主要因素之一，可以輕鬆修改該篩選以獲得一個數字的素數分解。所以我想知道使用它的素因子分解來生成所有因子會更有效率嗎？
設n = P 1 ^ķ * P ^ķ * .... * P_米^ķ_米

我認爲這種表示法可以在篩分後得到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 _我） ）。

所以我的問題是：
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; 
     } 
    } 
} 

我甚至沒有試過編譯它，所以要注意空載。