Least positive integer $n$ such that any set of $n$ pairwise relatively prime $>$ $1$ and $<$ $2005$ contains at least one prime number. 
Find the least positive integer $n$ such that any set of $n$ pairwise relatively prime integers greater than $1$ and less than $2005$ contains at least one prime number.    

The given solution of the above problem opens with the following line:  

The example $2^2, 3^2, 5^2,\dots, 43^2$ where we considered the squares of the first $14$ prime numbers, shows that $n\geq 15$.

How does this happen? Why are we considering squares of primes?
 A: The condition is: If we pick any arbitrary set of $n$ numbers so that all numbers in set are pairwise relatively prime then there exists a prime number in that set.
So, if $n \le 14$, then when we pick the set $\{ 2^2,3^2, \ldots , 43^2 \}$ (which has $14$ numbers in set) where there is no prime in this set, which contradicts to our condition. Thus, $n \ge 15$.
They choose squares of primes to guarantee that 


*

*All numbers are pairwise relatively prime. 

*The set doesn't contain any prime number.


If we can find set $A$ that guarantee this, then $n \ge |A|+1$ (the proof using contradiction is similar to when $|A|=14$). Thus, it suffices to find set $A$ with maximal number of elements.
Note that we can choose differently $$B= \{ 2 \cdot 997, 3 \cdot 661, 5 \cdot 397, 7 \cdot 269, 11 \cdot 173, 13 \cdot 151, 17 \cdot 113, 19 \cdot 103, 23 \cdot 83, 29 \cdot 67, 31 \cdot 61, 37 \cdot 53, 41 \cdot 47, 43^2 \}.$$ This also shows that $n \ge |B|+1=15$. It seems that $n=15$ is the smallest possible. 
The randomly chosen set $A$ is to show that $n \ge 15$. But that's not all the problem required, we also need prove that $n=15$ is the smallest possible. 
