Yinelemeli olarak n-1 faktoriyelini bulmanın alışılmış yolunu biliyorum ve sonra kontrol ediyorum. Ancak bu, O (n) 'nin karmaşıklığına sahiptir ve büyük n için çok zaman alır. Alternatif var mı?(n-1) 'i bulmanın hızlı bir yolu var mı? n tarafından bölünebilir mi?
Evet var: n bir öncelikli ise,n tarafından bölünemez. o a ve b içerdiğinden n bir asal değildir ve a != b ile n = a * b olarak yazılabilir Eğer
sonra (n-1)!n ile bölünebilir.
n = 4 ise (n-1)!n bölünebilir değil, ama a ile n = a * a bir asal sayı> 2 olmak eğer biz (yorumlarda Juhana sayesinde) a ve 2a(n-1)! bulmak çünkü (n-1)!n bölünemeyen bir.
n'yi en baştan bulmak için, 1'den n'ye kadar yinelemem gerekmeyecek mi? – batman
@ nearner nope, yalnızca 2'den 'zemine (sqrt (n))'. –
Naif bir yöntem, n'lerin bölenleri olup olmadığını görmek için 1 ile sqrt (n) 'arasında (ve n değil) sayıları test etmek olabilir, ancak bu başka bir soru (http://stackoverflow.com/questions)/2586596/en-algoritma için-asallık-testi). – alestanis