Why do you need the primes? You just need to precalculate using sieve. Anyway, this problem is pretty well known. You can easily find the solution on the internet.

You can solve this task using sieve in O(x log log x + N log x). You don't need different approach here.

If you are very interested, there is a method how to calculate all the divisors of the number in... well, something like O(n^(1/4)*log^2) using this algorithm.

But this task can be esily solved with sieve.

Naive O(NsqrtX) should work since X=10^6 and N=10^5 (so 10^8 operations). I'm calling sqrtX naive because it's pretty well known.

At least, I did that and got AC, so it should probably work for you.

There is also a very well known algotithm to compute divisors of all numbers $$$\le x$$$ in $$$O(x\log x)$$$.

for(int i=1;i<=x;i++){
    for(int j=i;j<=x;j+=i){
        divisors[j].push_back(i);
    }
}

This is $$$O(xH_x)$$$, which is well known to be $$$O(x\log x)$$$. This not only computes the number of divisors, but also stores all of them for all numbers.

Just in case you don't know $$$H_x$$$ you can read this

I used Pollard Rho's factoring with Miller Rabin primality test. I took the factoring from one of dacin21's submissions.

Submission

#define vector<int> vi;
vi v(N+1,0);
void factorize (vi v){
	for(int i=1;i<=N;i++)
		for(int j=i;j<=N;j+=i){
			v[j]+=1;
		}
	return v;
}

I used this to count the number of divisors for Atcoder Beginner Contest. Worked for me this is a similar to seive so i guess runtime is same as seive