Балканская олимпиада по математике 2011 года | Казахстанские олимпиады

Пусть $S$ конечное множество натуральных чисел, которое имеет следующее свойство: если $x$ — элемент $S$, то и все положительные делители $x$ также принадлежат $S$. Непустое подмножество $T$ множества $S$ назовем хорошим, если для любых чисел $x, y\in T$ и $x < y$ отношение $y/x$ является степенью простого числа. Непустое подмножество $T$ множества $S$ назовем плохим, если для любых чисел $x, y\in T$ и $x < y$, отношение $y/x$ не является степенью простого числа. Условимся, что одноэлементное подмножество $S$ одновременно является и хорошим и плохим. Пусть $k$ максимально возможный размер хорошего подмножества $S$. Докажите, что $k$ также является наименьшим числом попарно-непересекающихся плохих подмножеств, объединение которых дает множество $S$.