Простое число — это целое число большее \(1\), которое имеет ровно два делителя. Например, число \(7\) простое, так как имеет два делителя \(\{1, 7\}\). Составное число — это целое число большее \(1\), которое имеет более двух различных делителей.
Обратите внимание, что число \(1\) не является ни простым, ни составным.
Рассмотрим составное число \(v\). Оно имеет несколько делителей: некоторые делители простые, остальные сами составные. Если число простых делителей числа \(v\) меньше или равно числу составных делителей, назовем число \(v\) сильно составным.
Например, число \(12\) имеет \(6\) делителей: \(\{1, 2, 3, 4, 6, 12\}\), два делителя \(2\) и \(3\) — простые, в то время как три делителя \(4\), \(6\) и \(12\) — составные. Поэтому, число \(12\) сильно составное. Другие примеры сильно составных чисел: \(4\), \(8\), \(9\), \(16\) и так далее.
С другой стороны, делители числа \(15\) — это \(\{1, 3, 5, 15\}\): \(3\) и \(5\) простые, \(15\) составное. Поэтому, число \(15\) не сильно составное. Другие примеры: \(2\), \(3\), \(5\), \(6\), \(7\), \(10\) и так далее.
Вам даны \(n\) чисел \(a_1, a_2, \dots, a_n\) (\(a_i > 1\)). Вам необходимо построить массив \(b_1, b_2, \dots, b_k\) который удовлетворяет следующим условиям:
- Произведение всех элементов массива \(a\) равно произведению всех элементов массива \(b\): \(a_1 \cdot a_2 \cdot \ldots \cdot a_n = b_1 \cdot b_2 \cdot \ldots \cdot b_k\);
- Все элементы массива \(b\) целые больше \(1\) и являются сильно составными;
- Размер \(k\) массива \(b\) максимально возможный.
Найдите размер \(k\) массива \(b\), или сообщите, что нет массива \(b\) удовлетворяющего условиям.
Примечание
В первом набор мы можем получить массив \(b = [18]\): \(a_1 \cdot a_2 = 18 = b_1\); \(18\) является сильно составным числом.
Во втором наборе мы можем получить массив \(b = [60]\): \(a_1 \cdot a_2 \cdot a_3 = 60 = b_1\); \(60\) является сильно составным числом.
В третьем наборе нет массива \(b\) удовлетворяющего условиям.
В четвертом наборе мы можем получить массив \(b = [4, 105]\): \(a_1 \cdot a_2 \cdot a_3 = 420 = b_1 \cdot b_2\); \(4\) и \(105\) являются сильно составными числами.