Untitled

vector<int> count_divisors_linear(int n) {
    vector<int> divisors(n + 1);
    vector<int> primes;
    vector<int> min_prime(n + 1, 0);
    vector<int> exponent_count(n + 1, 0); // Count of the smallest prime factor in i

    divisors[1] = 1;

    for (int i = 2; i <= n; ++i) {
        if (min_prime[i] == 0) {
            min_prime[i] = i;
            primes.push_back(i);
            divisors[i] = 2;          // A prime has 2 divisors: 1 and itself
            exponent_count[i] = 1;    // p^1
        }
        for (int p : primes) {
            if (p > min_prime[i] || i * p > n) break;
            
            min_prime[i * p] = p;
            if (min_prime[i] == p) {
                // If p is already the smallest prime factor of i
                // (a+1) becomes (a+2) -> we divide by (a+1) and multiply by (a+2)
                exponent_count[i * p] = exponent_count[i] + 1;
                divisors[i * p] = divisors[i] / (exponent_count[i] + 1) * (exponent_count[i * p] + 1);
            } else {
                // If p is a new, smaller prime factor
                exponent_count[i * p] = 1;
                divisors[i * p] = divisors[i] * 2; // (a_1+1)... * (1+1)
            }
        }
    }
    return divisors;
}