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