Problem from ECPC qualifications day 2

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	165
2	maomao90	164
3	Um_nik	163
4	atcoder_official	161
5	adamant	160
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	nor	153
9	Dominater069	153

Hello codeforces. I am trying to upsolve the problems of qualification day2 of ECPC and i need some help on this problem.

The solution that i implemented was a dp solution where dp[i] is the answer for i. so before run any testcase i calculate the dp from 1 to 1e6, and to do this i cal min(dp[i-1]+1, dp[i/j]+j) where j is every divisor of i.

I tried different codes to make this fast and the fasted code that came in my mind was by generate all the prime divisors of i and then calculate the all the divisors of each i from its prime divisors.

But even this code take around more than 3 seconds on my machine. Can anyone please help me with this problem? I want to know if my idea was right and if so will this solution pass in the contest? unfortunately they don't write the time for each test case

Here is my CPP code

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

#define INF 1e18

using ull = unsigned long long;
using ll = long long;
using ui = unsigned int;

#define endl '\n'
#define newl cout<<endl;

void ICPC();

#define N 1000001
int dp[N+10];
int sp[N+10];
bool primes[N+10];

vector<int> getPD(int x) {
    vector<int> ret;
    while(x > 1) {
        ret.push_back(sp[x]);
        x /= sp[x];
    }
    return ret;
}

vector<int> st;
vector<int> tmp;

void genDiv(int ind, int val) {
    if(ind == tmp.size()) {
        st.push_back(val);
        return;
    }
    genDiv(ind+1, val);
    genDiv(ind+1, val*tmp[ind]);
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    memset(primes, 1, sizeof(primes));
    primes[0] = primes[1] = 0;
    sp[1] = 1;
    for(int i = 2; i <= N; i+=2) sp[i] = 2;
    for(ll i = 3; i <= N; i+=2) {
        if(primes[i]) {
            sp[i] = i;
            for(ll j = i; j*i <= N; j+=2)
                if(primes[j*i]) primes[j*i] = 0, sp[j*i] = i;
        }
    }
    dp[0] = dp[1] = 0;
    for(int i = 2; i < N; i++) {
        dp[i] = dp[i-1]+1;
        tmp = getPD(i);
        st.clear();
        genDiv(0, 1);
        for(auto &x : st) {
            dp[i] = min(dp[i], dp[i/x]+x);
        }
    }

    int t = 1;
    cin >> t;
    for(int i = 1; i <= t; i++) {
        ICPC();
        newl;
    }
}

void ICPC() {
    int n;
    cin >> n;
    int ans = 0, tmp;
    for(int i = 0; i < n; i++) {
        cin >> tmp;
        ans += dp[tmp];
    }
    cout << ans;
}