算法

(数学、构造)

可以构造 $A_i = i$ 的素因子个数 $+1$ 即可满足要求。

C++ 代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using std::cin;
using std::cout;
using std::vector;
using ll = long long;

// linear sieve
vector<int> ps, pf;
void sieve(int mx) {
    pf.resize(mx + 1);
    rep(i, mx + 1) pf[i] = i;
    for (int i = 2; i <= mx; ++i) {
        if (pf[i] == i) ps.push_back(i);
        for (int j = 0; j < ps.size() and ps[j] <= pf[i]; ++j) {
            int x = ps[j] * i;
            if (x > mx) break;
            pf[x] = ps[j];
        }
    }
}

int main() {
    int n;
    cin >> n;

    vector<int> a(n + 1, 1);
    sieve(n);

    for (int p : ps) {
        ll x = p;
        while (x <= n) {
            for (int i = x; i <= n; i += x) a[i]++;
            x *= p;
        }
    }

    a.erase(a.begin());
    for (auto x : a) cout << x << " ";

    return 0;
}