bat*_*man 9 iteration factorial
我知道通常的方法是迭代地找到n-1阶乘,然后检查.但是它具有O(n)的复杂性并且对于大n需要太多时间.还有其他选择吗？
ale*_*nis 15
是的,如果n是素数,显然(n-1)!是不能被整除的n.
如果n不是素数并且可以写成n = a * b,a != b则可以(n-1)!被整除,n因为它包含a和b.
如果n = 4,(n-1)!由是不可分的n,但如果n = a * a有a是一个素数> 2,(n-1)!是整除n,因为我们发现a和2a在(n-1)!(感谢Juhana在评论).