Автор задачі: | Ціцей Павло |
Задачу підготував: | Фейса Богдан |
Розбір написав: | Олександр Тимкович |
Якщо максимальний простий дільник більший за то відповідь . Це так, тому що щоб отримати добуток рівний , всі його прості дільники повинні бути використані.
Щоб знайти масив мінімальної довжини, можна слідувати такому жадібному алгоритму:
якщо число рівне то закінчити роботу.
нехай це максимальний дільник який не більший за . Записати в масив число та розділити на .
Знаходити дільник можна зі складністю O(\sqrt{x}).