Решение задачи Шерлок и его девушка с Codeforces

У Шерлока новая девушка (так необычно для него!). Приближается День Святого Валентина, и он хочет подарить ей украшения.

Шерлок купил n украшений. Цена i-го украшения равняется i + 1, то есть цены украшений равны 2, 3, 4, ... n + 1.

Ватсон поставил перед Шерлоком задачу раскрасить эти украшения так, чтобы два украшения имели разный цвет, если цена одного из них является простым делителем цены другого. Кроме того, Ватсон хочет, чтобы Шерлок использовал как можно меньше различных цветов.

Помогите Шерлоку выполнить это простейшую задачу.