Conosco il solito modo di trovare iterativamente n-1 in modo iterativo e poi di controllare. Ma questo ha una complessità di O (n) e richiede troppo tempo per il grande n. C'è un'alternativa?C'è un modo rapido per scoprire se (n-1)! è divisibile per n?
Sì, c'è: se n è un numero primo, ovviamente (n-1)! non è divisibile per n.
Se n non è un numero primo e può essere scritta come n = a * b con a != b poi (n-1)! è divisibile per n perché contiene a e b.
Se n = 4, (n-1)! non è divisibile per n, ma se n = a * a con a essere un numero primo> 2, (n-1)! è divisibile per n perché troviamo a e 2a in (n-1)! (grazie alla Juhana nei commenti).
per trovarlo n è primo, non dovrò iterare da 1 a n? – batman
@learner nope, solo da 2 a 'floor (sqrt (n))'. –
Un metodo ingenuo sarebbe quello di provare i numeri tra 1 e 'sqrt (n)' (e non 'n') per vedere se sono divisori di' n', ma questa è un'altra domanda (http://stackoverflow.com/questions/2586596/più veloce algoritmo-per-primalità-test). – alestanis