C Program: Check if a Given Number is a Prime

An integer n > 1 is a prime if its only divisors are 1 and itself. The number 2 is a prime because it is divisible only by 1 and itself. The number 3 is a prime as the only two integers dividing it are 1 and itself. And so is 5, 7, 11, 13, 17, ... and so on.

Here, we will be using the trial division method to check whether a given number is a prime or not. The method will be explained with examples in the following paragraphs.

Take the number 60. We get all its integer divisors as follows:

2, 3, 4, 5, 6, 10, 12, 15, 20, 30

Expressing it by factors,

60 = 2 x 30, 3 x 20, 4 x 15, 5 x 12, 6 x 10, 10 x 6, 12 x 5, 15 x 4, 20 x 3, 30 x 2

Notice that after 6, which is less than or equal to $\sqrt{60} \approx 7.74$, the products are merely a repeat in the reverse order as the first divisor is simply the dividend of a previous divisor. So, we just need to do divisibility tests from $2$ till $\sqrt{n}$.

Now take the number 29. As we know now that we only need to test with divisors less than or equal-to $\sqrt{29} \approx 5.386$. Those numbers would be 2, 3, 4 and 5. But since if an even number divides the number $n$, then so does 2. Which means, all even divisors after 2 are redundant and can be eliminated. So 4 is unnecessary. This leaves us with just 2, 3 and 5. And we find that 29 is not divisible by 2 or 3 or 5, so it must be prime.

But redundancy is not just for even numbers or multiples of 2, it applies the same for multiples of 3 as well. And next for 5, then 7, and so on. So, basically, we need to be dividing only with primes less than or equal to $\sqrt{n}$. This is the method of trial division.

But finding a set of primes to divide a number is another program in itself, so here we will not be filtering out the primes in our program.

We import the <math.h> library to make use of the sqrt() function. 

				
				#include <stdio.h>
				#include <math.h>
				int main() {
					unsigned short int i, n, flag = 0;
					printf("Enter a positive integer: ");
					scanf("%hu", &n);
					i = 2;
					while(i <= sqrt(n)) {
						if(n%i == 0) {
							flag = 1;
						}
						i++;
					}
					if(flag == 1) {
						printf("%hu is not a prime number \n", n);
					} else {
						printf("%hu is a prime number \n", n);
					}
					return 0;
				}

Here is the output of the program for the numbers 67, 83 and 79.