# Primality Test

·2 mins

Mayukh Datta

Problem Solving

Primality test is a test to determine whether a number is prime or not. There are many different primality tests.

## What is a prime number? #

A number is prime if it has exactly two positive whole number divisors, *one and itself*. On the other hand, a number is composite if it has more than two positive whole number divisors. Some interesting facts about prime numbers are: one is not a prime number since it does not satisfy the definition of being a prime, and there exist no even primes greater than 2.

## Now, let’s look at the naive approach #

To find if a number n is prime we could simply check if it divides any numbers below it.

C code:

```
#include<stdio.h>
#include<stdbool.h>
bool isPrime(long n);
int main(void){
long n;
printf("Enter the number for primality test: ");
scanf("%ld", &n);
printf("Result: %s\n", isPrime(n)?"Is a Prime.":"Not a Prime.");
}
bool isPrime(long n){
long i;
for(i=2; i<n; i++){
if(n%i == 0){
printf("It's divisible by %ld.\n", i);
return false;
}
}
return true;
}
```

Time complexity: \(O(n)\)

## The better approach #

- We only need to check divisibility for values of i that are less or equal to the square root of n
- Since there exist no even primes greater than 2. Therefore, after checking n is not an even number we can safely increment the value of i by 2 to avoid dividing n by odd numbers.

C code

```
#include<stdio.h>
#include<stdbool.h>
#include<math.h>
bool isPrime(long n);
int main(void){
long n;
printf("Enter the number for primality test: ");
scanf("%ld", &n);
printf("Result: %s\n", isPrime(n)?"Is a Prime.":"Not a Prime.");
}
bool isPrime(long n){
long i;
if(n<=1) return false;
if(n==2) return true;
if(n%2 == 0) return false; //even check
for(i=3; i<=sqrt(n); i+=2){ //increment by 2 to avoid checking odd nos.
if(n%i == 0){
return false;
}
}
return true;
}
```

Time complexity: \(O(√n)\)