China Western Mathematical Olympiad

First we prove $n\ge 16$. In fact, let $$A_0=\{1,2^2,3^2,5^2,\dots ,41^2,43^2\},$$ where the members in $A_0$, other than $1$, are the squares of prime numbers not greater than $43$. Then $A_0\subseteq S$, $|A_0|=15$ and the numbers in $A_0$ are pairwise coprime but $A_0$ contains no prime number. Thus $n\ge 16$.

Next we show that for arbitrary $A\subseteq S$ with $n=|A|=16$, if the numbers in $A$ are pairwise coprime, then $A$ must contain a prime number. In fact, if $A$ contains no prime number, denote $A=\{a_1,a_2,\dots ,a_{16};a_1<a_2<\cdots <a_{16}\}$. Then there are two possibilities.

(1) If $1\notin A$, then $a_1,a_2,\dots ,a_{16}$ are composite numbers. Since $(a_i,a_j)=1$ ($1\le i<j\le 16$), the prime factors of $a_i$ and $a_j$ are pairwise distinct. Let $p_i$ be the smallest prime factor of $a_i$. We may assume that $p_1<p_2<\cdots <p_{16}$, then $$a_1\ge p_1^2\ge 2^2,a_2\ge p_2^2\ge 3^2,\dots ,a_{15}\ge p_{15}^2\ge 47^2>2005,$$ it leads to a contradiction.

(2) If $1\in A$, let $a_{16}=1$, $a_1,a_2,\dots ,a_{15}$ are composite numbers. By the same assumption and argument of (1), we have $a_1\ge p_1^2\ge 2^2$, $a_2\ge p_2^2\ge 3^2$, $\dots ,a_{15}\ge p_{15}^2\ge 47^2>2005$. Again, it leads to a contradiction.

From (1) and (2), $A$ contains at least one prime number, i.e. when $n=|A|=16$, the conclusion is true. Thus, the minimum number of $n$ is $16$.