Нахождение всех взаимных подмножеств до числа N

Question

Предположим, у меня есть номера от 1 до N, и я хочу разделить их на подмножества на основе следующих критериев:

1. Каждое число может присутствовать только в 1 подмножестве.
2. Элементы подмножеств должны быть взаимно простыми соответственно в подмножествах. Например, для N = 5 я могу иметь как минимум два подмножества {1,2,3,5} и {4}. Но я не уверен, как распределить элементы в подмножествах, чтобы каждое подмножество имело взаимно простые элементы. Вот мой пошаговый подход:
   1. Набор 1: {все простые числа до N}
   2. Набор 2: {2 ^k , 3 ^k , 5 ^k ... p ^k }, где p - простое число, а p ^k k
   3. Остальные элементы

   Проблема в том, как получить элементы на шаге 3 взаимно простыми в подмножестве Может кто-то предложить лучший подход о том, как это реализовать и fl aws в моей логи c?

Answer 1

Кажется, это вопрос с подвохом. В одном и том же подмножестве не может быть двух четных чисел, поэтому минимальное количество подмножеств равно floor (n / 2)

Если n четное, вы можете легко достичь границы с подмножествами {2i + 1, 2i + 2}. Для нечетного n вы делаете то же самое, но помещаете {n-2, n-1, n} в последнее подмножество. Обратите внимание, что соседние числа всегда взаимно просты, а n, n-2 взаимно просты, если n нечетно.