我希望能够找到[1,107]中所有数字的因数。我知道这可以在O(sqrt(n))内解决。但是在此之前必须要运行埃拉托斯特尼筛法,可以轻松修改以获取一个数字的质因数分解(通过跟踪每个数字的一个质因数)。所以我想知道是否通过其质因数分解生成所有因数更有效率?
令n = p1k1 * p2k2*....*pmkm 我认为可以在筛选后的O(m+Σki)时间内得到这种表示。
经过一番思考,我想出了以下代码来生成因数:
令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)上面给出的代码可以优化吗?