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?
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