Почему просят дать именно такую информацию об ответе? Посмотрим на 2 числа $$$x + i$$$ и $$$x + j$$$, $$$i \lt j$$$. $$$\gcd(x + i, x + j) = \gcd(x + i, j - i) \le j - i$$$. То есть все НОДы маленькие, не больше $$$n$$$, а значит могут делиться только на простые до $$$n$$$. Ещё один способ это понять — такой. Чтобы НОД двух чисел делился на простое $$$p$$$, они оба должны на него делиться, но среди $$$n$$$ подряд идущих чисел максимум одно делится на $$$p \ge n$$$. Теперь посмотрим на $$$p \lt n$$$. На него будут делиться какие-то числа вида $$$x + r, x + r + p, x + r + 2p, \ldots $$$ где $$$r$$$ — это $$$p - x \% p$$$. Если этих чисел хотя бы 2, то каждое из этих чисел не может быть взаимнопросто со всеми остальными (поскольку есть те, НОД с которыми делится на $$$p$$$). То есть простое как бы "покрывает их". Теперь задача — покрыть все числа. Первая мысль — попробовать следующий жадник: переберём простые в порядке возрастания, для каждого остатка посчитаем, сколько ещё не покрытых чисел остаток покроет. Выберем лучший. К сожалению, этот жадник работает не всегда. Чтобы он начал работать, напишем поверх него рекурсивный перебор, который будет перебирать несколько возможных остатков в порядке убывания их выгодности. Добавим отсечение, что если простое число ничего нового не добавляет, то не запускаем ветку перебора. В это может быть сложно поверить, но на самом деле есть некоторая интуиция, почему перебор работает быстро. Сумма по $$$\frac{1}{p}$$$ расходится, хоть и очень медленно. Каждое простое число покрывает порядка $$$\frac{n}{p}$$$ чисел. Для $$$n \gt 70$$$ изначальный жадник уже начинает работать, а на маленьких $$$n$$$ веток перебора будет немного, не больше $$$3000$$$.