Programming Geek
Rated 4.7/5 based on 1446 reviews  ### Efficient Algorithm To Test Primality

Efficient Algorithm To Test Primality

A number which is greater than 1 is called prime if its only positive divisors are 1 and the number itself. A number which is not prime is called composite number. Suppose we have following numbers:

1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9

Then the prime numbers are : 2 , 3 , 5 , 7

and composite numbers are:  1 , 4 , 6 , 8 , 9

So to test whether a number is prime or not, the first employed approach is to divide the given number(n) by all numbers from 2 up to n-1 . If the number is divided perfectly then the number is not prime otherwise the number is prime.  Implementing this logic needs n-2 comparison, So the complexity is O(n).

Another approach to test primality is to divide n by all numbers from 2 upto n/2. Also this is not a good approach. It just reduces the number of comparison by half compared to previous approach.

An efficient algorithm to test primality is as follows:

1)      If n is less than 2 then n is invalid number.

2)     If n is equal to 2 then it is a prime number.

3)     If n is divisible by 2 then it is not prime. If n is not divisible by 2 then it won’t be divided by any even number.

4)     If n is prime then there must exist a divisor of n which is less than or equal to square root(n).

So, if n is less than 2 then it is not prime. If n is equal to 2 then it is a prime number.  If it is not divisible by 2 then it will not be divided by any even number. So we need to check only for odd numbers from 3 upto square root(n). Of course if n is prime then a divisor of n must be less than or equal to square root(n). In this approach we need to do (square root(n)/2)-1 comparison. So it is quite fast compared to other two approaches.

Here goes implementation of this efficient primality test algorithm in various languages:

JAVA implementation of primality test:

```//PrimeTest.java
import java.util.Scanner;

/**
*
* @author VIK VIKKU VIKASH VIKASHVVERMA
*/
public class PrimeTest {

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.println("Enter a number:");
int num = scanner.nextInt();
PrimeTest test = new PrimeTest();
if (test.isPrime(num)) {
System.out.println(num + " is a prime number!");
} else {
System.out.println(num + " is not a prime number!");
}

}

private boolean isPrime(int num) {
boolean flag = false;
if (num < 2) {
return !flag;
}
if (num == 2) {
return true;
}
if (num % 2 == 0) {
return flag;
}
int i = 3;
int rootn = (int) Math.sqrt(num);
for (; i <= rootn; i += 2) {
if (num % i == 0) {
break;
}

}
if (i > rootn) {
flag = true;
}
return flag;
}
}

```

C implementation of primality test:

```#include<stdio.h>

#include<math.h>

int isPrime(int num)

{

int i=3,rootn=sqrt(num);

if(num<2)

{

return 0;

}

if(num==2)

{

return 1;

}

if(num%2==0)

{

return 0;

}

for(;i<=rootn;i+=2)

{

if(num%i==0)

return 0;

}

return 1;

}

int main()

{

int num;

printf("Enter a number:");

scanf("%d",&num);

if(isPrime(num))

{

printf("%d is a prime number!",num);

}else

{

printf("%d is not a prime number!",num);

}

}

```

C++ implementation of primality test:

```#include<iostream.h>

#include<math.h>

int isPrime(int num)

{

int i=3,rootn=sqrt(num);

if(num<2)

{

return 0;

}

if(num==2)

{

return 1;

}

if(num%2==0)

{

return 0;

}

for(;i<=rootn;i+=2)

{

if(num%i==0)

return 0;

}

return 1;

}

int main()

{

int num;

cout<<"Enter a number:";

cin>>num;

if(isPrime(num))

{

cout<<num<<" is a prime number!";

}else

{

cout<<num<<" is not a prime number!";

}

}

```

#### 1 comment :

1. nice..
easy to understand.. :)