解题思路
先用埃氏筛预处理出所有不超过 106 的质数。
因为 n≤1018，如果存在质数 p 满足 p2∣n，那么 p≤109。
分两类讨论：
- 若 p≤106
P4956.第2题-找平方因子
题目内容
给你一个正整数 n，请你找出 n 的所有因子里，形如 p2 的因子，其中 p 是质数。换句话说，p2 必须整除 n，并且 p 必须是质数。
输入描述
每个测试文件均包含多组测试数据，第一行输入一个整数 T (1≤T≤300) 表示数据组数，此后对于每一组测试数据：
输入一个整数 n (1≤n≤1018).
输出描述
对于每一组测试数据，新起一行，按照从小到大的顺序输出所有满足条件的因子 p2，数与数之间用一个空格隔开。
如果不存在任何这样的因子，输出 −1。
样例1
输入
4
12
18
72
1000006000009
输出
4
9
4 9
1000006000009
说明
- 当 n=12 时，12=22⋅3，只有 22=4 是质数平方因子，输出为 4。
- 当 n=72 时，72=23⋅32，满足条件的因子有 22=4 和 32=9，按从小到大输出为 4 9。
