ghoshsai5000's blog

By ghoshsai5000, history, 7 years ago, In English

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 !

  • Vote: I like it
  • -12
  • Vote: I do not like it

| Write comment?