Auto comment: topic has been updated by aopo (previous revision, new revision, compare).

I mean how having atmost 9 distinct prime factors allows us to directly say YES/NO even without brute forcing for larger N?

Pick any number A. If (N+1)/2 >= 10 then for every prime p that divides A you can just pick one number that is not divisible by p. These <=10 numbers already have GCD=1 and you can pick any other numbers to make it (N+1)/2 total.

If you have a subset $$$S$$$ of size less than $$$ceil((N+1)/2)$$$ with $$$\gcd(S)=1$$$, you can insert to it any $$$ceil((N+1)/2)-|S|$$$ elements and it'll still satisfy the gcd condition. So your goal is to find any subset of size $$$\le ceil((N+1)/2)$$$ with $$$\gcd = 1$$$.

Fix any element $$$x$$$ in $$$B$$$ which must be included in $$$S$$$. $$$x$$$ can have at most 9 distinct prime factors. Let them be $$$p_1, \cdots, p_k, k \le 9$$$. Since $$$\gcd(B)=1$$$, for each $$$p_i$$$, $$$B$$$ must have an element $$$b_i$$$ which is not divisible by $$$p_i$$$ ($$$b_i$$$s can be equal). Then just set $$$S=\lbrace x, b_1, \cdots, b_k \rbrace$$$, and we must have $$$\gcd(S)=1$$$ since $$$\gcd(S)$$$ divides $$$x$$$ and none of the $$$p_i$$$ divides it. This set is enough to determine that the answer is YES if $$$|S| \le k+1 \le ceil((N+1)/2)$$$. Since $$$k \le 9$$$, this inequality always hold if $$$N \ge 18$$$.