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

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