First assume $p$ is prime and let the positive integers be $a_1, a_2, \cdots, a_{p+1/2}$. Since the values $\frac{a+b}{\gcd(a, b)}$ remain unaffected by scaling, divide all the $a_i$ with $\gcd(a_1, a_2, \cdots, a_n)$. Now suppose that $p \mid a_i$ for some $i$. Then from the gcd condition, there is $j$ with $p \nmid a_j$. Then $p \mid a_i/\gcd(a_i, a_j)$ forcing $\frac{a_i}{\gcd(a_i, a_j)} \geqslant p$ and then we can find $\frac{a_i+a_j}{\gcd(a_i, a_j)} \geqslant p$. Now suppose $p \nmid a_i$ for all $i$. By PHP there exist $i \ne j$ and $\epsilon \in \{-1, 1\}$ with $a_i+\epsilon a_j$ divisible by $p$. Since $p \nmid a_i, a_j$ we also have $p \nmid \gcd(a_i, a_j)$ and so $p \mid \frac{a_i+\epsilon a_j}{\gcd(a_i, a_j)}$ forcing \[\frac{a_i+a_j}{\gcd(a_i, a_j)} \geqslant \frac{|a_i+\epsilon a_j|}{\gcd(a_i, a_j)} \geqslant p\]as desired again. Now assume that $p = ab$ for $a, b > 1$ is a composite positive integer. Consider the following $p+1/2$ integers: We pick the first $a$ positive integers and after that the first $\frac{p+1}{2}-a$ even integers. It is not hard to see that in such a collection for any choice of integers $x, y$ from the selection we have $\frac{x+y}{\gcd(x, y)} < p$.