## Introduction

I've tried to harness C's speed and an efficient algorithm for prime number testing.

## Background

What you need to know is 2 facts.

- If the number can be factored into two numbers, at least one of them should be less than or equal to its square root.
- Every prime number can be represented by the form 6k+1 or 6k-1.

## Explanation

The two facts I just mentioned are converted to code here.

#include <stdio.h>
#include <math.h>
main()
{
unsigned long int testno;
unsigned long int i=0;
unsigned long int testsqrt;
printf("Enter number for checking : \n");
scanf("%lu",&testno);
if(testno==2||testno==3){
printf("\nPrime");
getch();
exit();}
if(((testno+1)%6==0)||(((testno-1)%6)==0)||(testno%2!=0)||(testno%3!=0))
{
testsqrt=ceil(sqrt(testno));
for(i=5;i<=testsqrt;i++)
{
if(i%2==0||i%3==0)
continue;
if(testno%i==0)
{
printf("\nNot Prime");
getch();
exit();
}
}
}
else
{
printf("\nNot Prime");
getch();
exit();
}
printf("\nPrime");
getch();
}

First, it checks if the number is 2 or 3 and if it is one of them, it prints that the number is prime.

The line:

if(((testno+1)%6==0)||(((testno-1)%6)==0)||(testno%2!=0)||(testno%3!=0))

filters out a majority of the non-prime numbers.

First, it tests if the number can be represented by the form 6k+1 or 6k-1 and then if it is a multiple of 2 or 3.

If it can be represented in either of the forms(6k+1 or 6k-1), then it proceeds to the checking loop.

If the condition fails, the program exits after printing `"Not Prime"`

.

Then, `testsqrt`

stores the square root of `testno`

(the number the user inputs).

The loop counter i starts from 5 (2 and 3 have been already checked. Every multiple of 4 is divisible by 2 which has already been checked too).

Then, the counter is checked if it is even or if it is a multiple of 3. If it is either, then the program proceeds to the next iteration.

Then, the program checks if `testno`

is a multiple of the current number(counter).

If it is, then the program prints `"Not Prime"`

.

If no number divides `testno`

, finally, the program prints that the number is prime and exits.