Program to Check Prime Number using Most Efficient sqrt(N)

// C program to check if a number is prime using most efficient sqrt(n)
#include <math.h>
#include <stdio.h>

// Function check whether a number
// is prime or not
int isPrime(int n)
{
	// Check if n=1 or n=0
	if (n <= 1)
		return 0;
	// Check if n=2 or n=3
	if (n == 2 || n == 3)
		return 1;
	// Check whether n is divisible by 2 or 3
	if (n % 2 == 0 || n % 3 == 0)
		return 0;
	// Check from 5 to square root of n
	// Iterate i by (i+6)
	for (int i = 5; i * i <= n; i = i + 6)
		if (n % i == 0 || n % (i + 2) == 0)
			return 0;

	return 1;
}

// Driver Code
int main()
{
	int N = 17;
	if (isPrime(N))
		printf("%d is a prime number", N);
	else
		printf("%d is not a prime number", N);
	return 0;
}

// This code is contributed by Susobhan Akhuli