factorial - if (n-1)! を見つける簡単な方法はありますか? nで割り切れますか？

Question

n-1階乗を繰り返し見つけてチェックする通常の方法を知っています。しかし、これには O(n) の複雑さがあり、n が大きいと時間がかかりすぎます。代替手段はありますか？

Answer 1

はい、あります:nが素数の場合、明らかに(n-1)!で割り切れませんn。

nが素数ではなくn = a * bwithのように書ける場合は、 と が含まれているため、a != bで(n-1)!割り切れます。nab

がで割り切れない場合でもn = 4、素数 > 2 の場合は で割り切れます(コメントの Juhana に感謝します) 。(n-1)!nn = a * aa(n-1)!na2a(n-1)!