论坛 › 难题征解 › 有避免完全因子分解，获得整数的平方因子的算法吗？

zeroieme 发表于 2016-12-7 13:00:58

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

如$15435=35*21^2$

zgg___ 发表于 2019-10-11 11:05:38

同问，呵呵。
p = NextPrime
q = NextPrime
n = p^2 q
FactorInteger // Timing
SquareFreeQ // Timing
MoebiusMu // Timing
从运行结果来看，貌似SquareFreeQ用的就是分解的方法。

zgg___ 发表于 2019-10-11 12:59:17

根据：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___ 发表于 2019-10-11 13:28:34

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

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