Задача 7. Один цвет для всех

Выбираем опорные числа

Возьмём $101,103,107,109$. Они простые: достаточно проверить делимость на простые $2,3,5,7$, потому что квадратный корень каждого меньше $11$. Все лежат в исходном диапазоне. Тройка $101,103,107$ попарно взаимно проста и имеет один цвет; тройка $101,103,109$ связывает с ним и четвёртое число.

Три простых уже слишком велики

Любое произведение трёх этих простых не меньше

Поэтому число $m$ из нашего диапазона не может делиться на три из них: тогда их произведение делило бы $m$, что больше самого $m$. Значит, хотя бы два опорных простых не делят $m$.

Связываем произвольное число с опорными

Назовём эти два простых $p,q$. Они различны и взаимно просты друг с другом. Поскольку простые $p,q$ не делят $m$, имеем $\gcd(m,p)=\gcd(m,q)=1$. Тройка $m,p,q$ попарно взаимно проста, поэтому её числа должны иметь один цвет. Цвет $p,q$ уже общий для всех четырёх опорных чисел.

Проверяем границы

Число $m$ выбиралось произвольно, включая $100$ и $1\,000\,000$. Если оно само равно одному из опорных простых, просто берём два других. Следовательно, все числа исходного диапазона обязаны иметь один общий цвет.