2012-10-21 10 views

risposta

15

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).

+0

per trovarlo n è primo, non dovrò iterare da 1 a n? – batman

+0

@learner nope, solo da 2 a 'floor (sqrt (n))'. –

+0

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