有没有办法缩短这段代码的执行时间？
有没有办法缩短这段代码的执行时间？
提问于 2015-10-31 18:11:13
我试图找到一个给定数字的所有除数之和，但我超过了时间限制，帮助我减少这个代码的时间限制。
int a,count=0;
cin>>a;
for(int i=2;i<=a/2;i++) {
if(a%i==0) {
count=count+i;
}
}
count++;
cout<<count;回答 4
Stack Overflow用户
回答已采纳
发布于 2015-10-31 18:20:04
我想说的是升到平方吨(A)。每次你有一个余数0，同时添加一个I和一个/i。你需要处理角落的情况，但这会降低时间的复杂性。取决于a有多大，这应该更快。对于较小的值，这实际上可能要慢一些。
Stack Overflow用户
发布于 2015-10-31 18:18:00
如果要将两个除数相加，则可以使循环运行到sqrt(a)，而不是a / 2：count += i + a / i。
Stack Overflow用户
发布于 2015-10-31 18:38:02
这个问题可以通过素因式分解来优化。
Let’s assume any number’s prime factor is = a ^n*b^m*c^k
Then, Total number of devisors will be = (n+1)(m+1)(k+1)
And sum of divisors = (a^(n+1) -1 )/(a-1) * (b^(m+1)-1)/(b-1) *(c^(k+1)-1)/(c-1)
X = 10 = 2^1 * 5^1
Total number of devisors = (1+1)(1+1) =2*2= 4
Sum of divisors = (2^2 – 1 ) /1 * (5^2 -1 )/4 = 3 * 24/4 = 18
1+2+5+10 = 18 页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/33454918
复制相关文章
相似问题
腾讯云开发者
