Олимпиада Туймаада по математике. Младшая лига. 2008 год

Докажите, что все составные натуральные числа, не превосходящие $10^6$, можно расставить по кругу так, чтобы никакие два соседних числа не были взаимно просты. ( А. Голованов )