Если n=pk для какого-то простого p, то тогда ответ равен p цветам. Тогда просто надо покрасить все плитки с номерами i(modp) в цвет i. Так как любой делитель d числа n больше 1 делится на p, то любые две плитки i и i+d будут покрашены в одинаковый цвет. К тому же, если первые p плиток покрашены в c разных цветов, то следующие p плиток будут покрашены в те же c цветов, поэтому ответ не может превосходить p.

Если же n=pq для p,q>1 таких, что gcd(p,q)=1, тогда ответ равен 1. Рассмотрим любые две разных позиции i,j. Докажем, что их цвет должен совпадать. По китайской теореме остатов, существует такой 1≤x≤n, что x≡i(modp) и x≡j(modq). Поэтому, обе плитки i и j должны быть покрашены в тот же цвет, что и плитка x. Значит, все плитки должны быть покрашены в один и тот же цвет.

Чтобы проверить, который случай из двух выполняется, используем слеlующий алгоритм:

Сначала проверяем, является ли n простым. Используем стандартный O(n−−√) алгоритм.
Иначе, если n=pk для k>1, тогда p должен быть по крайней мере n−−√≤106. Тогда мы можем найти наименьший делитель p числа n, больше 1, так как он не превышает 106. Тогда делим n на наибольшую степень p. Если n=pk, тогда n просто станет 1; иначе n останется больше 1, тогда он делится на какое-то другое простое, отличное от p.
Время работы: O(sqrt(n)).