Решение задачи Ихаб и особая задача о раскраске с Codeforces

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

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

Для каждой пары целых чисел (i,j), если i и j взаимно просты, то ai≠aj.
Максимальное значение всех ai должно быть минимальным (то есть как можно меньшим).
Два натуральных числа называются взаимно простыми, если их наибольший общий делитель равен 1.

Код 

#include <bits/stdc++.h>
using namespace std;
int n,i,j,k,a[222000];
int main()
{
	cin >> n;
	for(i = 2; i <= n; i++)
	{
		if(a[i] == 0)
		{
			j++;
			for(k = i; k <= n; k += i)
                a[k] = j;
		}
	}
	for(i = 2; i <= n; i++) 
        cout << a[i] << " ";
    return 0;
}

         

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




Комментарии

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


© 2020 HSECODES [email protected] Карта сайта