有避免完全因子分解，获得整数的平方因子的算法吗？

zeroieme

如$15435=35*21^2$

zgg___

同问，呵呵。

1. p = NextPrime[2 10^22]
   
2. q = NextPrime[3 10^22]
   
3. n = p^2 q
   
4. FactorInteger[n] // Timing
   
5. SquareFreeQ[n] // Timing
   
6. MoebiusMu[n] // Timing

复制代码

从运行结果来看，貌似SquareFreeQ用的就是分解的方法。

zgg___

根据：http://mathworld.wolfram.com/Squarefree.html，如下：

There is no known polynomial time algorithm for recognizing squarefree integers or for computing the squarefree part of an integer. In fact, this problem may be no easier than the general problem of integer factorization (obviously, if an integer n can be factored completely, n is squarefree iff it contains no duplicated factors). This problem is an important unsolved problem in number theory because computing the ring of integers of an algebraic number field is reducible to computing the squarefree part of an integer (Lenstra 1992, Pohst and Zassenhaus 1997).

zgg___

https://arxiv.org/abs/1304.6937
在这里有一篇相关论文