4. Let $n \geqslant 2$ be a natural number. Let $S$ be a subset of the set $\{1,2, \ldots, n\}$ that does not contain two relatively prime elements, nor two elements where one divides the other. What is the maximum number of elements that the set $S$ can have?

(Romania)
4. For every $x \in S$ there exists a unique $k_{x} \in \mathbb{N}_{0}$ such that $\frac{n}{2}<2^{k_{x}} x \leqslant n$. Let $f(x)=2^{k_{x}} x$. The mapping $f$ is injective: indeed, if for $x, y \in S$ we have $f(x)=$ $f(y)$, then $x \mid y$ or $y \mid x$, so by the condition of the problem $x=y$. Therefore, the set $f(S)=\{f(x) \mid x \in S\}$ has the same cardinality as the set $S$. Moreover, $f(S)$ does not contain two consecutive numbers (since they are coprime), so $|f(S)| \leqslant\left[\frac{n-\left[\frac{n}{2}\right]+1}{2}\right]=\left[\frac{n+2}{4}\right]$.

On the other hand, the set $S=\left\{2 i \left\lvert\, \frac{n}{4}<i \leqslant \frac{n}{2}\right.\right\}$ has exactly [ $\frac{n+2}{4}$ ] elements and satisfies the conditions of the problem. Therefore, the answer is $\left[\frac{n+2}{4}\right]$.