Олимпиадный тренинг

Задача . C. Ихаб и особая задача о раскраске


Вам дано целое число \(n\). Для каждого целого числа \(i\) от \(2\) до \(n\) найдите положительное целое число \(a_i\) такое, что выполняются следующие условия:

  • Для каждой пары целых чисел \((i,j)\), если \(i\) и \(j\) взаимно просты, то \(a_i \neq a_j\).
  • Максимальное значение всех \(a_i\) должно быть минимальным (то есть как можно меньшим).

Два натуральных числа называются взаимно простыми, если их наибольший общий делитель равен \(1\).

Входные данные

Первая строка содержит одно целое число \(n\) (\(2 \le n \le 10^5\)).

Выходные данные

Выведите \(n-1\) целое число \(a_2\), \(a_3\), \(\ldots\), \(a_n\) (\(1 \leq a_i \leq n\)).

Если существует несколько решений, выведите любое из них.

Примечание

Обратите внимание, что \(3\) и \(4\) взаимно просты, поэтому \(a_3 \neq a_4\). Также обратите внимание, что \(a=[1,2,3]\) удовлетворяет первому условию, но это неправильный ответ, поскольку максимальное число равно \(3\).


Примеры
№Входные данныеВыходные данные
1
4
1 2 1
2
3
2 1
Статистика успешных решений по компиляторам
 Кол-во
С++5