Sashko-Array Constructor#7

Sashko-Array Constructor (Editorial)

Problem Author:

Tsitsei Pavlo

Problem Setter:

Bogdan Feysa

Editorialist:

Oleksandr Tymkovich

If the maximum prime divisor of is greater than , then the answer is . This is because to obtain a product equal to , 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 , then finish the work.

  • let be the maximum divisor of that is not greater than . Write the number to the array and divide by .

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