factorial - 有没有一种快速查找 if (n-1) 的方法！能被n整除吗？

Question

我知道迭代查找 n-1 阶乘然后检查的常用方法。但这具有 O(n) 的复杂性，并且对于大的 n 需要太多时间。有替代方案吗？

Answer 1

是的：如果n是素数，显然(n-1)!不能被 整除n。

Ifn不是素数并且可以写成n = a * bwith a != bthen(n-1)!可以被整除，n因为它包含a和b。

如果n = 4,(n-1)!不能被 整除n，但如果n = a * a是a素数 > 2，(n-1)!则可以被 整除，n因为我们发现a和2ain (n-1)!（感谢 Juhana 在评论中）。