#O1110. 最大质因子

最大质因子

题目描述

给定 TT 个正整数 nin_i,对每个 nin_i 求出它的最大质因子。若 nin_i 为质数,答案就是它本身。

输入格式

第一行一个整数 TT。

接下来 TT 行,每行一个正整数 nin_i。

输出格式

共 TT 行,每行一个整数,表示对应 nin_i 的最大质因子。

样例 #1

样例输入 #1

3
4
15
1000000000000000000

样例输出 #1

2
5
5

数据规模与约定

数据范围 说明
1≤T≤201 \le T \le 20 询问个数
2≤ni≤10182 \le n_i \le 10^{18} 待分解的数
  • 若 nin_i 为质数,直接输出 nin_i。
  • 建议使用 Miller-Rabin 判素与 Pollard-Rho 分解,乘法请使用 __int128 防止溢出。