22-я Балканская математическая олимпиадаЯссы, Румыния, 2005 год

Дано целое число $n \geq 2$. Пусть $S$ — подмножество множества $\{1,2,\dots,n\}$ такое, что $S$ не содержит два элемента, один из которого делит другого, и не содержит два элемента, которые взаимно просты. Найдите максимально возможное количество элементов такого множества $S$.