Problem from ECPC qualifications day 2

#	User	Rating
1	tourist	4009
2	jiangly	3839
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3612
7	Geothermal	3569
8	ecnerwala	3494
9	Um_nik	3396
10	gamegame	3386

#	User	Contrib.
1	Um_nik	164
2	-is-this-fft-	162
3	maomao90	159
3	atcoder_official	159
5	cry	158
5	awoo	158
7	adamant	155
8	nor	154
9	TheScrasse	153
10	Dominater069	152

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;
}