Task 5. A set $S$ consisting of 2019 (distinct) positive integers has the following property: the product of any 100 elements of $S$ is a divisor of the product of the remaining 1919 elements. What is the maximum number of prime numbers that $S$ can contain?
Solution. The maximum number of prime numbers is 1819.

We start with the construction. Choose different prime numbers $p_{1}, p_{2}, \ldots, p_{1819}$ and let $P=p_{1} p_{2} \cdots p_{1819}$. Take

$$
S=\left\{p_{1}, p_{2}, \ldots, p_{1819}, P, P \cdot p_{1}, \ldots, P \cdot p_{199}\right\}
$$

For each $p_{i}$, there are 201 numbers in $S$ that are divisible by $p_{i}$ (namely $p_{i}$ and all numbers divisible by $P$). Of these, at most one number has two factors $p_{i}$; the rest have one factor $p_{i}$. If we take 100 numbers from $S$, then their product contains at most 101 factors $p_{i}$. Among the remaining numbers, there are still at least 101 numbers divisible by $p_{i}$, so their product has at least 101 factors $p_{i}$. Since this holds for every $p_{i}$ and the numbers in $S$ have no other prime factors, this means that $S$ has the desired property.

We now prove that $S$ cannot contain more than 1819 prime numbers. Consider a prime divisor $q$ of a number in $S$. Suppose that at most 199 numbers in $S$ are divisible by $q$. Then we take the 100 elements of $S$ with the most factors $q$; these always have more factors $q$ in total than the remaining elements, contradicting the condition in the problem. Therefore, there must be at least 200 numbers in $S$ that are divisible by $q$. If there are exactly 200, it follows that the number of prime factors $q$ in all these numbers must be the same, otherwise we get a contradiction again if we choose the 100 elements with the most factors $p$.

We now see that $S$ must contain at least 199 non-prime numbers, because a prime number $p$ in $S$ divides at least 199 other elements of $S$. Suppose now that $S$ contains exactly 199 non-prime numbers. Then the prime factor $p$ appears in each of these 199 non-prime numbers exactly once (namely just as often as in the prime number $p$). Furthermore, numbers in $S$ cannot be divisible by a prime number $r$ that is not in $S$, because then there must be at least 200 multiples of $r$ in $S$ and that would be 200 non-prime numbers, a contradiction. This means that each of the 199 non-prime numbers in $S$ must be the product of the prime numbers in $S$ and in particular these 199 numbers are not distinct from each other. This is a contradiction, so $S$ must contain at least 200 non-prime numbers and thus at most 1819 prime numbers.