Wilson’s Theorem to find prime number

Wilson’s Theorem states that a natural number is p > 1 is a prime number if only if the below condition is met.


  (p - 1) ! ≡  -1   mod p 
 OR  (p - 1) ! ≡  (p-1) mod p

For example, Take p as 4
(4 – 1)! = 3 ! => 3 * 2 * 1 = 6
(6 % 4) != 3 => 6 not equals to 3
So p is not a prime number.

Take p as 5
(5-1)! = 4 ! => 4*3*2*1 = 24
24%5 == 4
4 == 4
So p is a prime number.

Refer the below code to know how to do with a java program.


import java.util.Scanner;

public class PrimeFInder {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int number = scanner.nextInt();
        System.out.println("The entered number is "+number);

        //  (p - 1) ! ≡  (p-1) mod p
        int lhs = getFactorialValue(number- 1) % number;
        int rhs = number - 1;
        if(lhs == rhs){
            System.out.println("Its a prime number");
        }else{
           System.out.println("Its an non prime number");
        }
    }

    private static int getFactorialValue(int n) {
        int value = 1;
        for (int i = 1; i <= n; i++) {
            value *= i;
        }
        return value;
    }
}

The output is given below,


12
The entered number is 12
Its an non prime number


Advertisements