Think of how to check if a number x is a gcd of a subsequence.

If there is such subsequence, then all of it will be divisible by x. Moreover, if you divide each number in the subsequence by x , then the gcd of the resulting numbers will be 1.

Adding a number to a subsequence cannot increase its gcd. So, if there is a valid subsequence for x , then the subsequence that contains all multiples of x is a valid one too.

Iterate on all possiblex from 1 to 10^5, and check if there is a valid subsequence for x.