Sashko-Array Constructor

Problem Author: | Tsitsei Pavlo
Problem Setter: | Bogdan Feysa
Editorialist: | Oleksandr Tymkovich

If the maximum prime divisor of $$$x$$$ is greater than $$$d$$$, then the answer is $$$-1$$$. This is because to obtain a product equal to $$$n$$$, all its prime divisors must be used.

To find an array of minimum length, you can follow the same greedy algorithm:

- if the number is equal to $$$1$$$, then finish the work.
- let $$$k$$$ be the maximum divisor of $$$x$$$ that is not greater than $$$d$$$. Write the number $$$k$$$ to the array and divide $$$x$$$ by $$$k$$$.

Finding the divisor can be done with a complexity of $$$O(\sqrt{x})$$$.