2
我想查找範圍內的所有數字因子[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)上面給出的代碼可以優化嗎?