Half primes in the set

Question

Let S be 30 element subset of {1,2,....2015} such that every pair of elements in S are relatively prime. Prove that at least half of the elements in S are prime numbers

Answer 1

Here's an outline of the proof:

• Show that there are $14$ primes under $\sqrt{2015}$.
• Let $R$ be a set of $14$ composite coprime numbers under $2015$. It is well-known that any composite number has a prime factor under its square root, so in this case, each of these composite numbers has one of the prime factors under $\sqrt {2015}$. Now, using that knowledge, show that there is no composite number coprime to all of the numbers in $R$ because otherwise, there would have to be a fifteenth prime under $\sqrt{2015}$.
• Now, you have shown that no more than $14$ composite numbers under $2015$ can be coprime. Using that knowledge, prove that at least $16$ elements in $S$ are prime or $1$ and thus there are at least $1% primes in $S$, concluding the proof.