#YS261106. 寻找素数

寻找素数

题目描述

小武得到了一个正整数 nn。他想知道,能不能把 nn 写成两个素数的乘积。

素数是指在大于 11 的自然数中,除了 11 和它本身以外不再有其他因数的数。注意 11 不是素数。

如果能写成两个素数的乘积,请按从小到大的顺序输出这两个素数;如果不能,输出 −1-1。

输入格式

一行一个整数 nn。

输出格式

如果存在两个素数 p,qp,q 满足 p≤qp \le q 且 p⋅q=np \cdot q = n,输出一行两个整数 p,qp,q,中间用一个空格隔开。

否则输出一行一个整数 −1-1。

样例

6
2 3
21
3 7
100
-1

样例解释

  • 样例 1:6=2×36=2\times 3,且 2,32,3 都是素数,所以输出 2 3。
  • 样例 2:21=3×721=3\times 7,且 3,73,7 都是素数,所以输出 3 7。
  • 样例 3:100=2×2×5×5100=2\times 2\times 5\times 5,素因子个数(按重数计)为 44,不是两个素数的乘积,所以输出 -1。

数据范围与约定

  • 2≤n≤10122 \le n \le 10^{12}