CF BUDDY
← Problems·

797A · k-Factorization

1100 · implementation, math, number theory

Problem: Given a positive integer n, find k integers (not necessary distinct) such that all these integers are strictly greater than 1, and their product is equal to n.

Input Format: The first line contains two integers n and k (2 ≤ n ≤ 100000, 1 ≤ k ≤ 20).

Output Format: If it's impossible to find the representation of n as a product of k numbers, print -1.

Otherwise, print k integers in any order. Their product must be equal to n. If there are multiple answers, print any of them.

Sample Cases

Case 1

Input

100000 2

Output

2 50000

Case 2

Input

100000 20

Output

-1

Case 3

Input

1024 5

Output

2 64 2 2 2

Similar problems

00:00:00
Loading editor…
Welcome! I'm your coding tutor for this problem. Use the chips below to reveal stored hints or get AI feedback on your code. I'll guide you step by step — never giving away the solution.

Sign in to unlock AI tutor feedback