Number of test cases is 10^5.

For each test case, N can be as large as 10^5. So for each test case time complexity would be atleast O(N) as we will have to take the input.

Total time complexity would be O(N*t)=O{10^10)

Is it possible to solve the question with runtime 2sec??

The sum of values of

Nin each test file does not exceed100000

I have used prime sieve to calculate prime numbers till 10^5 and stored it in a array in ascending order.

then for each test case, calculated the gcd for the input and checked for the smallest prime that divide this gcd.

Isn’t it a good approach?

No.

Consider the test case

```
100000
1
99877
1
99877
...
```

This test case would absolutely kill your code because there are \pi(max(A))=O(\frac{max(A)}{\log(max(A))}) primes, and T test cases. So your time complexity is

O(T\pi(max(A)) + \sum Nlog(max(A)) + max(A)\log(\log(max(A))))

Which won’t pass the constraints.

First term is iterating through all primes, second term is calculating GCD, and third term is sieve.

If you can’t figure out how to solve it, you can read my answer.

## How to solve it

Use a set instead of a vector, And check whether res is a prime using the

`prime.count(res)`

It will return 1 if res is a prime. Then output res directly. If it’s not, then iterate through all elements in the set.

This is faster because a composite number x has at least one prime less that \sqrt{x}.

Your new time complexity is

O(T\pi(\sqrt{max(A)}) + \sum Nlog(max(A)) + max(A)\log(\log(max(A)))log(max(A)))

Which will pass

CodeChef: Practical coding for everyone

got it. Thank you

Can you help me understand the syntax you used while iterating through elements in the set??

for(auto &ans : prime)

That’s just syntax, there’s not much to explain.

`auto`

-use whatever datatype the set contains

`&`

- don’t create an extra copy of the value.

Do **NOT** put this if you’re going to change the value.

`ans`

- what name you want the variable to have

`:`

- you can read this as “In”, so` : prime`

becomes in set prime.