[AdditionalFile6466.zip](file://AdditionalFile6466.zip?type=additional_file)

#6466. 分解质因数

标签: 传统 | 时间限制: 5000 ms | 内存限制: 1024 MiB |

题目描述

输入一个数 $n$，已知它为两个不同质数的乘积，请输出这两个质数。

输入格式

一行一个整数 $n$。

输出格式

一行两个用空格分割的整数 $p$、$q$，满足$1<p<q<n$，$n=pq$。

样例 1

输入

543589

输出

233 2333

样例 2

输入

998244359987710471

输出

998244353 1000000007

样例 3

输入

900811415596911720447323

输出

900000000013 1000901572871

样例 4

输入

998802351736664963004207092321

输出

998901948141863 999900294112567

数据范围与提示

对于20%的数据，$n < 10^7$。

对于40%的数据，$n < 10^{12}$。

对于60%的数据，$n < 10^{18}$。

对于80%的数据，$n < 10^{25}$。

对于100%的数据，$6 \leq n < 10^{30}$。

每个subtask10个点，数据比较随机。

提示：loj可以使用 __int128。