#O1110. 最大质因子
最大质因子
题目描述
给定 个正整数 ,对每个 求出它的最大质因子。若 为质数,答案就是它本身。
输入格式
第一行一个整数 。
接下来 行,每行一个正整数 。
输出格式
共 行,每行一个整数,表示对应 的最大质因子。
样例 #1
样例输入 #1
3
4
15
1000000000000000000
样例输出 #1
2
5
5
数据规模与约定
| 数据范围 | 说明 |
|---|---|
| 询问个数 | |
| 待分解的数 |
- 若 为质数,直接输出 。
- 建议使用 Miller-Rabin 判素与 Pollard-Rho 分解,乘法请使用
__int128防止溢出。