我想找到范围[1,107]中所有数字的除数 . 我知道它可以在O(sqrt(n))中解决 . 但是在此之前必须运行Eratosthenes的筛子,这可以很容易地修改以获得一个数字的素数因子化(通过跟踪每个数字的一个主要因素) . 所以我想知道使用其素数因子分解生成所有因子会更有效吗?
设n = p1k1 * p2k2 * .... * pmkm
我认为这种符号可以在筛子后在O(mΣki)中获得 .
经过一番思考后,我想出了以下代码来生成因子:
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 ki)) .
所以我的问题是:
1)以这种方式生成因子比通常更快(O(sqrt(n))循环方法)?
2)上面给出的代码可以优化吗?
1 回答
第一个最明显的优化是预分配答案向量 . 你确切知道会有多少因素(因为你已经把公式给了Π(1 ki)) .
如果您自己管理堆栈而不是使用递归,那么您将获得最佳解决方案(每个因素只需要1次查找和1次乘法) .
像这样的东西?
我甚至没有尝试过编译它,所以请注意 .