Getting TLE

I am getting TLE for the last sub task of this

I also have a couple of doubts.

  1. If I am finding primes upto 10^3 or 10^4 I am getting WA for last two sub tasks. I think I should get AC for that.

  2. If I replace all[j]<=arr* with all[j]all[j]<=arr, I am getting WA for last two sub tasks. Shouldn’t this be right? I mean shouldn’t we check it up to square root of the number?

  3. And finally, what can be done to improve my solution?

My solution