a740: 質因數之和

 a740: 质因数之和

題目來源 https://zerojudge.tw/ShowProblem?problemid=a740

顧名思義，求質因數的和。求因數當然不難，但這題的測資最大接近20億，如果是跑回圈一個一個檢測，難保不會TLE(超時)，給幾個優化的思維。

1.將收到的數開根號，找2到測資開根號之間有沒有因數。

2.質數只可能出現在6A+1或6A-1的地方。

以下附上程式碼：

如果有不懂得地方歡迎來信或留言。

#include <iostream>
#include <math.h>

using namespace std;


int main()
{
    cin.tie(0) , cin.sync_with_stdio(0);
    int n , sum;
    while(cin >> n) {
        if(n <= 1) {
            cout << 0;
            continue;
        }
        sum = 0;
        while(n % 2 == 0) {
            sum += 2;
            n /= 2;
        }
        while(n % 3 == 0) {
            sum += 3;
            n /= 3;
        }
        int a = sqrt(n) + 1;
        for(int i = 6; i < a; i++) {
            
            while(n % (i - 1) == 0) {
                sum += (i - 1);
                n /= (i - 1);
            }
            while(n % (i + 1) == 0) {
                sum += (i + 1);
                n /= (i + 1);
            }
        }
        if(n != 1) sum += n;
        cout << sum << "\n";
    }

    return 0;
}