orl wrote: Is it possible to arrange on a circle all composite positive integers not exceeding $ 10^6$, so that no two neighbouring numbers are coprime? Author: L. Emelyanov

This reminds me of USAMO 2005, Problem 1. So you could arrange many numbers with a factor of 2, ending with 6, then arrange many numbers with a factor of 3, ending with 15, and so on... right?

$ ....x\cdot y,1,2\cdot a_1,2\cdot a_2,...,2\cdot3,3\cdot b_1,...,3\cdot5,5\cdot c_1,......$ where $ a_1$ is the biggest prime such that $ 2\cdot a_1\leq10^6$, and so on, until we arrive at $ x\cdot y$. So in this way we have arranged all the composite numbers not exceeding $ 10^6$ that are a product of exactly two prime numbers. So now if we take a remaining number $ \alpha$, then $ \alpha$ is a product of at least three prime numbers: $ (\beta,\gamma,\delta)$ (not necessarily distinct). Wlog $ \beta\leq\gamma\leq\delta$, so we can put $ \alpha$ beside $ \beta\cdot\gamma$.