C++

10.cpp

/*
Compile: 
g++ -O2 --std=c++11 10.cpp

Run:     
time ./a.out

Results with g++ version 4.8.4:  
sum(20000000) = 12272577818052 in 0.019s
sum(200000000) = 1075207199997334 in 0.063s
sum(2000000000) = 95673602693282040 in 0.310s
sum(20000000000) = 2*10^10 * 2*10^10 overflows 64 bit long long in line 35 (***)
*/

#include <unordered_map>
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int main(int argc, char** argv) {
    long long n = 20000000;
    int r = sqrt(n);
    vector<long long> V;
    for (int i = 1; i <= r; i++) {
        V.push_back(n / i);
    }
    for (int i = V.back() - 1; i > 0; i--) {
        V.push_back(i);
    }
    unordered_map<int, long long> S(2 * r);
    for (int i = 0; i < V.size(); i++) {
        const long long v = V[i];
        S[v] = v * (v + 1) / 2 - 1; // (***)
    }
    for (int p = 2; p <= r; p++) {
        if (S[p] > S[p - 1]) {
            for (int i = 0; i < V.size(); i++) {
                const long long v = V[i];
                if (v < p * p) {
                    break;
                }
                S[v] -= p * (S[v / p] - S[p - 1]);
            }
        }
    }
    cout << "sum(" << n << ") = " << S[n] << endl;
    return 0;
}