求约数的高效办法，自问自答

来源：百度知道 编辑：UC知道 时间：2024/05/31 03:16:26
看到网上的求约数的办法，都差不多，我的办法基本公式也一样，不过可以少循环次数。复杂度为<1.5sqrt(数字)
因为约数都有一个中间数，
如128 中间数是11
1 2 4 8 (11) 16 32 64 128
算到前一半，自然就算到后一半
问题是这个中间数怎么算出来，对于128中的11怎么算出来，自然是128的开平方根。
下面是我的代码：
int mid = sqrt (128);//最好是取整，忘了取整的函数了，如果用类型转换可能得到的结果为12
int* divisors = new int [mid];
for (int i = 1; i <= mid; i++) {
if (128%i == 0){
cout << i << endl;
divisors[i-1] = 128/i;
}
}
divisors[i] = 0;
i = 0;
while (divisors[i]!=0) {
cout << divisors[i] << endl;
i++;
}
delete divisors[];
现在分析一下复杂度
以128为例子
如果从头到尾都算需要128次循环
而用我的方法只需11+4＝15
11为前一半的循环
4是根据前一半算出来的后一半的约数的显示循环

应该还有更好的办法，也许可从一个数的质数方面想。
其实，不是算得出得数就算完了，还要想想效率。

// 求n的约数
vector<pair<int, int> > v = primeFactor(n); // 分解成素数的积
vector<int> factor; //存放约数
int sz=v.size();

int bound=1;
for(int j=0; j<sz; j++) // 采用数字电路加1法枚举约数
bound*=(v[j].second+1); // 求出最大值bound..

for(int j=0; j<bound; j++) ...{ // 0 ~ bound-1
int fac= 1;
int q=j;
for(int k=0; q && k<sz; k++) ...{ // 模出每一位取几个
int tt=q % (v[k].second+1);
for(int a=0; a< tt; a++)
fac*=v[k].first;
q/=(v[k].second+1);
}
factor.push_back(fac);
}

自问自答属于作弊，要承担法律责任！

如果我发现有问题，一定会举报的！