Program to Check Prime Numbers using Wilson’s Theorem

// We will evaluate the (N-1)! + 1, where N is the given number.
// Then we will check the divisibility of (N – 1)! + 1 with N, i.e. ((N – 1)! + ) % N == 0.
// If the remainder is zero, then N is a prime number.
// If the remainder is not zero, then N is not prime.

#include <stdio.h>

// utility function to evaluate factorial
long long int getFactorial(int n)
{
	long long int f = 1;
	for (int i = 2; i <= n; i++) {
		f *= i;
	}
	return f;
}

// function to check prime number
void checkPrime(int N)
{

	long long fact = getFactorial(N - 1);

	if (fact % N == N - 1) {
		printf("The number %d is a prime number.", N);
	}
	else {
		printf("The number %d is not a prime number.", N);
	}

	return;
}

// driver code
int main()
{
	int N = 17;

	checkPrime(N);

	return 0;
}