Powerful Divisors

• Time : $O(n\sqrt{max(A)})$
• Space : $O(max(A))$

int dp[1010101];
int helper(int n) {
    if(n == 1) return 1;
    if(dp[n]) return dp[n];
    int& res = dp[n];
    int N = n;
    bool fl = true;
    for(int i = 2; i <= sqrt(N) and fl; i++) {
        if(N % i) continue;
        int c = 1;
        while((N % i) == 0) {
            N /= i;
            c++;
        }
        fl = __builtin_popcount(c) == 1;
    }
    return res += helper(n-1) + fl;
}

vector<int> Solution::powerfulDivisors(vector<int> &A) {
    vector<int> res;
    for(auto& a : A) {
        res.push_back(helper(a));
    }
    return res;
}