ABC300G TLE

#include <assert.h>
#include <bits/stdc++.h>
using namespace std;

template <class T> using mpq = priority_queue<T, vector<T>, greater<T>>;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vl = vector<ll>;
using vi = vector<int>;

vi primes;
void get_primes(ll ub)
{
    for (int i = 2; i <= ub; ++i) {
        for (int j = 2; j * j <= i; ++j)
            if (i % j == 0)
                continue;
        primes.push_back(i);
    }
}

ll res;
constexpr int cap = 1 << 16;
ll dp[32][cap];

void dfs(ll n, int p)
{
    if (n < cap && dp[p][n]) {
        res += dp[p][n];
        return;
    }

    if (p == 0) {
        res += __lg(n) + 1;
        return;
    }

    // fprintf(stderr, "dfs(n:%lld, p:%d)\n", n, p);
    ll cache = res;

    dfs(n, p - 1);
    if (n >= primes[p])
        dfs(n / primes[p], p);

    if (n < cap)
        dp[p][n] = res - cache;
}

int main(int argc, char **argv)
{
    ll n, p;
    cin >> n >> p;
    get_primes(p);

    dfs(n, primes.size() - 1);

    cout << res << endl;
    return 0;
};