33OJ
登录 注册

#D1038. 寻找素数

寻找素数

题目描述

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

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

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

输入格式

一行一个整数 nn,保证 nn 是偶数。

输出格式

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

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

样例

6
2 3
4
2 2
8
-1

样例解释

样例 1 中,6=2×36=2\times3,且 2,32,3 都是素数,所以输出 2 3。

样例 2 中,4=2×24=2\times2,两个因子都是素数,所以输出 2 2。

样例 3 中,8=2×48=2\times4,但 44 不是素数;其余分解也找不到两个素数,所以输出 −1-1。

数据范围与约定

子任务 分值 限制
11 3030 2≤n≤1062 \le n \le 10^6
22 7070 2≤n≤10122 \le n \le 10^{12}

对于 100%100\% 的数据,保证 2≤n≤10122 \le n \le 10^{12} 且 nn 是偶数。