Нахождение максимального подмножества

[Lodyr]

Задали задачку на С++следующего содержания:
Дан массив натуральных чисел, найти самое большое подмножество элементов, в котором любые два элемента имеют одинаковое множество простых делителей.

Нахождение всех простых делителей числа я нахожу без проблем. Беда только в том, каким способом находить это максимальное подмножество.

Я так полагаю:
если дан к примеру массив: 1 5 15 30 и 45 из 5 элементов.
Для каждого из них: 1(1), 5(1,5), 15(1,3,5), 30(1,2,3,5), 45(1,3,5) множества простых делителей.
Значит максимальное подмножество = {15 и 45}.

Кроме как отсортировать массив по возрастанию в зависимости от простого делителя каждого элемента я предложить ничего не могу.
Подкиньте идею поиска =(

Вот что высянил = с помощью нахождения НОДа двух чисел можно определить = одинаковое ли у них множество простых делителей или нет.
так можно понять у чисел 15, 45 и 55 = 3 простых делителя
но вот 55 отличается тем, что отличается элементом 11 тогда как у двух впереди идущих он 3
НОД(15 и 45) = 15, одному из чисел по которому имкали НОД = значит множество простых делителей у них одно и тоже
а вот при нахождении НОД(15 и 55) и НОД(45 и 55) он будет равен 5, значит множества простых делителей отличаются и такие два элемента нам не подойдут.