Ich kenne die übliche Art, n-1 Fakultät iterativ zu finden und dann zu überprüfen. Aber das hat eine Komplexität von O (n) und braucht zu viel Zeit für großes n. Gibt es eine Alternative?Gibt es einen schnellen Weg zu finden, wenn (n-1)! ist teilbar durch n?
9
A
Antwort
15
Ja, es gibt: wenn n
ist eine Prime, offensichtlich (n-1)!
ist nicht durch n
teilbar.
Wenn n
keine Primzahl ist und als n = a * b
mit a != b
geschrieben werden, dann ist (n-1)!
teilbar durch n
weil es a
und b
enthält.
Wenn n = 4
ist (n-1)!
nicht teilbar durch n
, aber wenn n = a * a
mit a
eine Primzahl ist> 2, ist (n-1)!
teilbar durch n
weil wir a
und 2a
in (n-1)!
(dank Juhana in den Kommentaren) zu finden.
um es zu finden n ist prime, muss ich nicht iterieren über 1 bis n? – batman
@learner nope, nur von 2 bis 'floor (sqrt (n))'. –
Eine naive Methode wäre, Zahlen zwischen 1 und 'sqrt (n)' (und nicht 'n') zu testen, um zu sehen, ob sie Teiler von' n' sind, aber das ist eine andere Frage (http://stackoverflow.com/questions)/2586596/Schnellster-Algorithmus-für-Primalitäts-Test). – alestanis