Problem 11.6. Oleg wrote down several composite natural numbers less than 1500 on the board. It turned out that the greatest common divisor of any two of them is 1. What is the maximum number of numbers that Oleg could have written down?
Answer: 12.

Solution. Prime numbers less than $\sqrt{1500}$ will be called small. There are exactly 12 such numbers: $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37$.

Note that each of Oleg's numbers has a small divisor (otherwise it would be not less than $43^{2} > 1500$), and different numbers have different small divisors (otherwise the GCD of these numbers would be greater than 1). Therefore, the number of Oleg's numbers is no less than the total number of small numbers, i.e., no less than 12.

An example with 12 numbers is easy to construct: these are the numbers $2^{2}, 3^{2}, 5^{2}, 7^{2}, 11^{2}, 13^{2}, 17^{2}, 19^{2}, 23^{2}, 29^{2}, 31^{2}, 37^{2}$.