Maximum Sum of Factors of Numbers in a given Range

Question

This is a question I've been doing on some online judge platform.

Find the maximum sum of factors of numbers from 1 to N.

For instance, if N were to be 11, the answer will be 18. The number with the greatest sum of factors from 1 to 11 is 10 (1 + 2 + 5 + 10).

I implemented a relatively straightforward solution that looks like a sieve. The code in C++ is as shown below:

for (int i = 1; i <= 1000000; ++i {
    for (int j = i; j <= 1000000; j += i) {
        num[j] += i;
    }
    mx[i] = max(num[i], mx[i - 1]);
}

Whenever the user queries for some N, I simpy output mx[N]. This solution seems to be correct. However, it exceeds time limit(1s) for larger inputs. Maximum N is 1,000,000 but the user may query for 1,000,000 different values of N. The above code is a pre-processing code that is run once.

The complexity of the above code is N + N / 2 + N / 3 + ... + 1 which I suppose is about N Log N. How do I improve the complexity of this code?

Thank you for your help.

Answer 1

The answer of this problem is: Highly Abundant Number
You can get sequence from here: A002093

Actually, I checked that all highly abundant number below 10^10 is 41-smooth number, and below 10^13 is 61-smooth number.
N-smooth number can factorize primes below N.
You can search n-smooth number like this algorithm (ex. 47-smooth number below 10^16):

vector<int> p = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47 };
vector<long long> s = { 1 }; long long lim = 10000000000000000;
for (int i = 0; i < p.size(); i++) {
    vector<long long> w;
    for (long long j : s) {
        long long mul = j;
        for (; mul <= lim; mul *= p[i]) w.push_back(mul);
    }
    s = w;
}

You can factorize N-smooth number X in O(log N + log X), so you can calculate divisor function for O(log N + log X).

I give a result of my code, for example, I calculated all 61-smooth numbers below 10^13, in 3.5 sec, using 1GB of memory.