9

I know the usual way of finding n-1 factorial iteratively and then checking. But that has a complexity of O(n) and takes too much time for large n. Is there an alternative?

batman
  • 5,022
  • 11
  • 52
  • 82

1 Answers1

15

Yes there is: if n is a prime, obviously (n-1)! isn't divisible by n.

If n is not a prime and can be written as n = a * b with a != b then (n-1)! is divisible by n because it contains a and b.

If n = 4, (n-1)! isn't divisible by n, but if n = a * a with a being a prime number > 2, (n-1)! is divisible by n because we find a and 2a in (n-1)! (thanks to Juhana in comments).

alestanis
  • 21,519
  • 4
  • 48
  • 67
  • to find it n is prime, won't I have to iterate over 1 through n? – batman Oct 21 '12 at 11:18
  • A naive method would be to test numbers between 1 and `sqrt(n)` (and not `n`) to see if they are divisors of `n`, but that's another question (http://stackoverflow.com/questions/2586596/fastest-algorithm-for-primality-test). – alestanis Oct 21 '12 at 11:19
  • 4
    What about perfect squares? 4 is not a prime, but `3! / 4 = 1.5`. – JJJ Oct 21 '12 at 11:24
  • @Juhana ouch! you got me! Edited my answer. – alestanis Oct 21 '12 at 11:25
  • It's still not quite correct; `9 = 3 * 3` and `8! / 9 = 4480` (because `8!` is divisible by `3*6` which is `3*3*2`). – JJJ Oct 21 '12 at 11:36
  • Hmm... Would 4 be an exception? All other perfect squares give (n-1)! divisible by (n) then – alestanis Oct 21 '12 at 11:39
  • if `n=a*a`, `(n-1)!` divided by `a^2` is `(a-1)!*(a+1)*(a+2)*...*(n-1)` divided by `a`. So, either `a` divides `(a-1)!`, which is a recursive instance of original problem, or if not we need to check if `a` divides the upper half product `(n-1)!/a!` . In general, `2*a` will be among the multiplicands, if `a>2`, because `n=a*a`. E.g. for `8!/9 = (2)*(4*5*6*7*8) / 3`, `3*2` is among the upper product multiplicands, so `3` indeed divides it once more. So yes, 4 is an exception. This works regardless whether `a` is prime or not: `4*4=16, 4*2=8`, `16|(15!) === 4|(1*2*3)*(5*6*7*8*..*15) === true`. – Will Ness Oct 22 '12 at 10:30
  • Yes, n=4 (perfect square) is an exception: for all n > 5 holds that n is a composite number if and only if (n=1)! mod n = 0, in other words: (n-1)! is divisable by n if and only if n is not a prime. Whether or not the factors in n are different is irrelevant. See, for instance http://en.wikipedia.org/wiki/Factorial – Bert te Velde Oct 25 '12 at 15:48
  • @alestanis: You are tremendously profound intellectual mind.... :0 Great and inspiring :) – Jasmine Feb 25 '13 at 22:03