Solution of Wilson

Let us consider two disjoint cases:

1. N is a composite number. In this case, we wish to use the factorization of N:
   • If N can be written as a product of two different integers (N = A × B, 1 < A < B < N), it means that both A and B appear in the product 1 × 2 × … × (N-1). Therefore, N divides the product.
   • If N cannot be written as a product of two different integers, it means that N can be written as a product of two identical integers (remember that N is a composite number). Each of the two numbers is equal to sqrt(N).
     Because 1 < sqrt(N) < 2×sqrt(N) < N for any N greater than 4^[1], both square roots will appear somewhere in the product 1 × 2 × … × (N-1). Therefore, sqrt(N) × sqrt(N) = N divides the product.
   
   

   ^[1]: N = 4 is a particular case and should be dealt with independently.
   

2. N is a prime number. In this case, we make use of Lagrange's Theorem, which states that the residue classes (mod N) are a field. This means that every non-zero integer a has a unique multiplicative inverse a^-1.
   • For the most part, a ≠ a^-1. These means that we can match elements in pairs such that each pair has a product congruent to 1 (mod N).
   • However, there might be some elements a for which a ≡ a^-1 (mod N). This is equivalent to a² ≡ 1 (mod N). Because a polynomial of degree 2 has at most 2 roots in any field (again, Lagrange), we can be sure that the only values of a for which the previous equation holds are ±1. This means that ±1 (or 1 and N-1, if you wish) are their own multiplicative inverses. As a consequence, we cannot pair 1 with itself, and we cannot pair N-1 with itself. However, we can pair 1 with N-1, and get a multiplicative residue of N-1.
   Now we have (N-3)/2 pairs with products congruent to 1, and exacty one pair with the product congruent to N-1. The following expression will hold: 1 × 2 × … × (N-1) ≡ N-1 (mod N). Therefore, the answer in this case is N-1.

You can find more info on Wikipedia's article on Wilson's theorem.

The problem is reduced to determining whether or not N is a prime number. This can be solved in O(sqrt(N)) time complexity.

Python solution (Sergiu Puscas)

    1 import math
    2 n = input()
    3 
    4 print 2 if n == 4 else (0 if any(n % x == 0 for x in range(2, int(math.sqrt(n))+1)) else n-1)

Ruby solution (Croitoru Radu Bogdan)

    1 require 'prime'
    2 
    3 n = gets.chomp.to_i
    4 puts n==4? 2:(Prime.prime?(n)? n-1:0)

C++ solution (Gabriel Inelus)

    1 #include <iostream>
    2 int N, p;
    3 int main() {
    4     std::cin >> N;
    5     for(int i = 2; i * i <= N && !p; ++i)
    6         p |= (N % i == 0);
    7 
    8     if(N == 4) std::cout << 2;
    9     else if(p) std::cout << 0;
   10     else std::cout << N - 1;
   11 
   12     return 0;
   13 }