Menu
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?
807
Since in the factorial term the highest number present is 'n-1' the product i.e. the numerator can never be expressed with terms of 'n+1' if 'n+1' is prime. Hence divisibility is never possible. In any other case whether 'n+1' is even or odd but not 'prime' the divisibility is always possible.
C supports a modulo operator % , that evaluates remainder on division of two operands. You can use this to check if a number is exactly divisible by some number or not. For example - if(8 % 2) , if the given expression evaluates 0 , then 8 is exactly divisible by 2.
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).
191
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
