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!";

  }

  }