【C++】以最快的速度求一个数的因数之和

源代码： 

#include<iostream>
using namespace std;
int main(){
    int a,b=0;
    cin>>a;
    for(int i=2;i<a;i++){
        if(a%i==0){
            b+=i;
        }
    }
    cout<<b;
}

　　上面的源代码看似整洁，但实际上如果数无限大，例如8亿，那么程序也就会运行8亿次。

　　我们来举个例子。

　　100的因数(除1和他本省)有2、50、4、25、5、20、10。发现只要算到数的一半，就可以了。

我们就可以把代码优化成这样：

#include<iostream>
using namespace std;
int main(){
    int a,b=0;
    cin>>a;
    for(int i=2;i<=a/2;i++){
        if(a%i==0){
            b+=i;
        }
    }
    cout<<b;
}

　　但这样还是不够优化。

　　我们发现因数都是成对成对的，还是前面的那个例子，2和50一组，4和25一组，5和20一组，10和10一组(只算1次)。

　　我们可以一次添加两个数:

b+=i+a/i;

　　这样就可以了。

　　这是还有一个问题，就是要运行多少次呢？

　　如果i和前面加的数重复，那么程序就该停止了。我们知道i是不断增加的，而a/i是不断减少的。我们只要让i一定小于等于a/i，就不会重复。不妨设想一下，如果i>a/i;那么i的平方就一定大于i*a/i也就是a。所以我们得出，如果i*i>a，那么程序就要暂停了。

因此，我们得出代码：

#include<iostream>
using namespace std;
int main(){
　　int a,b=0;
　　cin>>a;
　　for(int i=2;i*i<=a;i++){
　　　　if(a%i==0){
　　　　　　b+=i;
　　　　}
　　}
　　cout<<b;
}

　　我们最后关注一下i是a的平方根的情况。

　　这里我们就直接用if else来判断：

if(i*i==n) b+=i;
else b+=i+a/i;

就得出了最快速的方法：

#include<iostream>
using namespace std;
int main(){
    int a,b=0;
    cin>>a;
    for(int i=2;i*i<=a;i++){
        if(a%i==0){
            if(i*i==n) b+=i;
            else b+=i+a/i;
        }
    }
    cout<<b;
}

这个代码虽然没有第一个代码整洁，但运行速度却已经提高了好几倍了。