Удаление И Сортировка Чисел В Массиве

[akisha]

Есть задачка:
Даны N положительных целых чисел, которые не делятся ни на какие простые числа, кроме 2 и 3. Требуется выкинуть минимально возможное количество чисел так, чтобы из любых двух оставшихся одно делилось на другое.
Никак не могу понять алгоритм действий(
Как можно решить эту задачку?

 

[guinevra]

Можно попробовать так: найти минимальный элемент, найти все элементы массива, на него делящиеся (не считая сам элемент, но учитывая равные ему), назначить "потомками". Далее повторять эту процедуру для "потомков". Очевидно, процесс закончится. Получится дерево, из которого нам надо оставить самую длинную ветвь.

 

[Whatka]

guinevra неплохая идея,но процесс не закончится,что возможно неочевидно)
пример: 2 3 4 9 27

то есть,если доработать,то: отсортировать массив,завести массив того же размера типа bool (все значения изначально = false)
проделать,то же,что говорилось раньше,помечая использованные хотя бы один раз числа как true
создать новое дерево для элемента с индексом,равным индексу числа в булевом массиве со значением false.


и мой вариант (тоже с деревом):
отсортировать массив и(начиная с меньшего) строить бинарное дерево по правилу:
если элемент делится на вершину,то в правое поддерево,если нет в левое,если нет
соответствующего поддерева -создать.
Найти самую глубокое правое поддерево.