Znam typowy sposób na znalezienie silni n-1 iteracyjnie, a następnie sprawdzanie. Ale to ma złożoność O (n) i zajmuje zbyt dużo czasu dla dużego n. Czy istnieje alternatywa?Czy istnieje szybki sposób na sprawdzenie, czy (n-1)! jest podzielna przez n?
Tak, istnieje: jeśli n jest podstawowym, oczywiście (n-1)! nie jest podzielny przez n.
Jeśli n nie jest najlepszym i może być zapisany jako n = a * b z a != b następnie (n-1)! jest podzielna przez n ponieważ zawiera ona a i b.
Jeśli n = 4, (n-1)! nie jest podzielna przez n, ale jeśli n = a * a z a jest liczbą pierwszą> 2, (n-1)! jest podzielna przez n ponieważ znajdujemy a i 2a w (n-1)! (dzięki Juhana w komentarzach).
aby znaleźć n jest najważniejsza, czy nie będę musiał powtarzać od 1 do n? – batman
@learner nope, tylko od 2 do 'floor (sqrt (n))'. –
naiwny sposób będzie test liczb od 1 do 'sqrt (n)' (nie 'n'), aby sprawdzić, czy są one dzielnikami' n', lecz inny zapytania (http://stackoverflow.com/questions/2586596/test najszybszego algorytmu dla pierwszorzędności). – alestanis