64位无符号整数最大无平方因子除数（Radical）快速算法探究

一、常规计算思路 #

radical(n)的核心是取n所有不同质因子的乘积，常规方法依赖质因数分解：

• 对n做质因数分解，得到n = p1^k1 * p2^k2 * ... * pn^kn
• 将每个质因子取一次相乘，即rad(n) = p1 * p2 * ... * pn

对于64位无符号整数，可以用Pollard's Rho算法快速分解，配合Miller-Rabin素性测试判断因子是否为质数，这套组合在64位范围内效率极高，能快速完成分解。

二、无需完全因式分解的快速算法 #

确实存在不需要完全分解n的方法，核心思路是通过迭代消除平方因子、提取不同质因子，避免对每个因子做彻底的质数分解：

1. 迭代式平方因子消除+质因子提取 #

• 步骤1：初始化rad = 1，当前数m = n
• 步骤2：用Miller-Rabin测试判断m是否为质数：
  • 如果是，将rad *= m，结束计算
  • 如果不是，用Pollard's Rho快速找到一个非平凡因子d
  • 计算g = gcd(d, m/d)：
    • 若g == 1，说明d和m/d互质，递归计算rad(d)和rad(m/d)，相乘后赋值给rad
    • 若g > 1，说明g是m的一个质因子的幂次，提取该质因子p（可通过迭代除以g结合Miller-Rabin测试验证），将rad *= p，然后把m除以p的所有幂次（即m = m / p^k，k为p在m中的指数），回到步骤2

2. 利用GCD与幂次快速提取小质因子 #

对于包含小质因子的n，可通过以下方式快速定位：

• 选择小整数a（如a=2），计算g = gcd(a^m - a, m)（m为当前处理数），若g>1且g<m，g即为m的非平凡因子，进一步处理该因子即可。这种方法能快速剥离小质因子，减少后续分解压力。

关键优势说明 #

无需完全因式分解的方法，本质是在分解过程中只保留每个质因子一次，不用计算每个质因子的具体幂次，因此在处理大64位整数时，比完全分解后再计算rad(n)更高效，尤其是当n包含高次幂质因子时，能节省大量计算步骤。

内容的提问来源于stack exchange，提问作者Simon Goater