797A.md (865B)
1 Source: https://codeforces.com/problemset/problem/797/A 2 3 A. k-Factorization 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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*. 22 23 Input 24 25 The first line contains two integers *n* and *k* (2 ≤ *n* ≤ 100000, 1 ≤ *k* ≤ 20). 26 27 Output 28 29 If it's impossible to find the representation of *n* as a product of *k* numbers, print -1. 30 31 Otherwise, print *k* integers in any order. Their product must be equal to *n*. If there are multiple answers, print any of them. 32 33 Examples 34 35 Input 36 37 ``` 38 100000 2 39 ``` 40 41 Output 42 43 ``` 44 2 50000 45 ``` 46 47 Input 48 49 ``` 50 100000 20 51 ``` 52 53 Output 54 55 ``` 56 -1 57 ``` 58 59 Input 60 61 ``` 62 1024 5 63 ``` 64 65 Output 66 67 ``` 68 2 64 2 2 2 69 ```