4. Piercarlo chooses $n$ integers from 1 to 1000 inclusive. None of his integers is prime, and no two of them share a factor greater than 1 .
What is the greatest possible value of $n$ ?
Solution
First, note that $31^{2}=961$ and $37^{2}=1369$, so the largest prime less than $\sqrt{1000}$ is 31 .
So any non-prime number less than 1000 (excepting 1) must have at least one prime factor which is less than or equal to 31 (otherwise the number would be at least $37^{2}$, which is larger than 1000 ).

We are told that all pairs of Piercarlo's share no factors greater than one; this clearly must include prime factors, and in particular the primes from 2 to 31 inclusive. Hence each of the primes up to 31 can only appear in the factorisation of one of his numbers.
So to maximise $n$, he will need to choose numbers with as few of these prime factors in their prime factorisation as possible. Indeed, he should aim to choose a set of numbers where each number he chooses has no more than one prime factor less than or equal to 31 . Since there are 11 of these primes, the maximum value of $n$ is 12 (since he can also pick 1 ).
It is easy to check that he can indeed pick 12 non-prime numbers less than 1000 - for example by picking 1 together with the squares of all the primes up to 31 :
$$
\{1,4,9,25,49,121,169,289,361,529,841,961\} .
$$