如何快速找出恰有4个因数的大数的所有因数？

已知满足 0 < n < 2×10^18 且恰有4个因数的数n，只有两种结构：

• 两个不同质数的乘积（记作 p*q，p≠q）
• 某个质数的立方（记作 p³）

基于这个结构特性，我们可以找到远快于O(√n)的方法来找出所有因数：

步骤1：先判断n是否为质数的立方 #

1. 计算n的立方根近似值 k = round(n ** (1/3))
2. 验证 k³ 是否等于n，同时用快速质数测试（如Miller-Rabin）验证k是否为质数
3. 若验证通过，n的因数为：1、k、k²、n

步骤2：若不是立方数，则n必为两个不同质数的乘积 #

1. 使用Pollard's Rho快速因数分解算法找出n的一个质因数p
2. 计算另一个质因数 q = n / p
3. n的因数为：1、p、q、n

为什么这个方法更快？ #

传统O(√n)算法对于2×10^18级别的数需要遍历约10^9次，耗时极长；而Miller-Rabin质数测试、Pollard's Rho因数分解都是亚线性时间复杂度的算法，对于10^18级别的数，能在毫秒级完成计算。

内容的提问来源于stack exchange，提问作者Jukasz Lewandowski