是否有快速查找if（n-1）的方法！可以被n整除？

Question

我知道通常的方法迭代找到n-1階乘，然後檢查。但是這具有O（n）的複雜性，並且需要太多的時間來處理大n。有其他選擇嗎？

Answer 1

是的，如果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因爲我們發現(n-1)!a和2a（感謝Juhana在評論）。