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

Без пояснения   Просмотров: 10


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

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

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

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

Код

#include<bits/stdc++.h>
using namespace std;
int p[9000005];
int main()
{
    int n;
    cin>>n;
    cout<<((n<3)?1:2);
    cout<<endl;
    n++;
    for(int i=2;i<=n;i++)
    {
        for(int j=i;j<=n;)
            p[j+=i]=1;
        cout<<1+p[i]<<" ";
    }
    return 0;
}

         

 Администратор Photo Автор: Администратор


Отправить решение задачи
Чтобы отправить решение вам нужно войти в систему или зарегистрироваться

Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться