Why is time limit exceeded?
A_i can be upto 10^6. Consider the array where N = 10 and all elements are equal to 10^6. So, even O(\sqrt N) will give TLE if you multiply and find factors in traditional way. Use a Seive to precompute the prime factors beforehand