So, I adopted two different approaches to the problem T-Primes ...

In the first solution, I maintained a set of all squares of Primes ... So, the complexity should be O(D log log D + N log S),

Where D = 1e6, N is the number of queries and S is the size of the set ... Each query on a set takes O(log S) time at most because it is a balanced tree.

In the second solution, I only maintained a vector of primes and checked if a number is a square root and if the square root is prime.

Here the solution is O(D log log D + T), where T is the complexity of finding square root of T ... I am unable to analyse ...

I know finding N^2 is easier than finding root(N) ... Can someone explain why one solution is better than the other ?

Help in understanding the complexities of the solutions would be much appreciated !