Problem 3. The numbers $2,3,4, \ldots, 29,30$ are written on the board. For one ruble, you can mark any number. If a number is already marked, you can freely mark its divisors and numbers that are multiples of it. What is the minimum number of rubles needed to mark all the numbers on the board? [6 points]

(I.V. Yashchenko)
Answer. For 5 rubles.

Solution. Let's mark the numbers $17, 19, 23$, and 29, spending four rubles. Then mark the number 2, spending another ruble. After this, we can freely mark all even numbers (since they are divisible by 2), and then all odd numbers not exceeding 15 - for any of them (let's say for the number $n$), the even number $2n$ is marked, and we can mark $n$ as its divisor. It remains to mark 21, 25, and 27, and this is also done for free: 25 is divisible by the marked number 5, and 21 and 27 are divisible by the marked number 3. In any way of solving the problem, the prime numbers 17, 19, 23, and 29, which exceed 15, will have to be marked for money, as they are not divisors or multiples of any numbers on the board. So, 4 rubles will be spent only on them. To mark anything else, we will have to spend a fifth ruble. Therefore, it is impossible to fulfill the conditions of the problem for less than five rubles.

Comment. In fact, after marking the "large" prime numbers, we could have marked any of the remaining numbers on the board instead of two. Indeed, then we will freely mark its smallest prime divisor $p$. If $p=2$, we act according to the algorithm described above. If not, we mark $2p$ (this is possible since $p<15$), then mark two, and then everything else in the known way.

A similar solution is applicable for an arbitrarily long set $2, 3, 4, \ldots, N$ - we are forced to mark all "large" prime numbers (exceeding $N / 2$) for money, and then mark any of the remaining numbers for a ruble. Then we freely mark two in the way described above, then all even numbers, then all "small" prime numbers (not exceeding $N / 2$), because any "small" $p$ will be a divisor of $2p$. Now we can mark all other unmarked numbers: each of them will be divisible by its minimal prime divisor - a "small" prime number.