Efficient ways to check if number is prime number

Problem
How to check if number is prime or not

You may remember that a prime number is one whose only factors are itself and 1. Other numbers are called oblong numbers (they can be represented as an oblong of dots) or composite numbers.

If you have a number and you want to find out if it's prime, that is called performing a primality test. The naive approach is to check all numbers m from 2 to sqrt(n) and verify that n % m is not 0. If you want to expand this slightly, you can throw out all even numbers (except 2). There are also some other enhancements to this naive approach that might improve performance, along with other, more advanced techniques.

Example
2 is a prime number :P

Solution

Method 1 - Brute force (find factor till N)

The traditional approach is,

bool isPrime(int x)
{
  if(x <= 1)
    return false;
  for(int i = 2; i < x; i++)
    if(x%i == 0)
      return false;
  return true;
}

This will however will loop through all elements below x to see if a factor exists. Example, for finding if 13 is prime, we check if its divisible by 2,3,4,....12. This can be optimized to loop through only half the elements since the highest factor is going to be num/2 as,
1b) Till N/2

bool isPrime(int x)
{
  if(x <= 1)
    return false;
  for(int i = 2; i < x/2; i++)
    if(x%i == 0)
      return false;
  return true;
}

But by analysis you can see that for a number say 100, the factors are (1*100),(2*50),(4*25),(5*20),(10*10),(20*5),(25*4),(50*2),(100*1). For finding out if 100 is prime or not we just need to check if 100 is divisible by any number not greater than 10 i.e., it is sufficient to check from 2 to 10. The reason being if its divisible by 4, its also divisible by 25.
1c) Till sqrt(N)

bool isPrime(int x)
{
  if(x <= 1)
    return false;
  for(int i = 2; i < sqrt(x); i++)
    if(x%i == 0)
      return false;
  return true;
}

Though these are ok approaches, but there are many good approaches available.

Method 2 - Pre-Computation using Sieve of Eratosthenes and Binary Search
Another approach would be to build a list of primes first using the Sieve of Eratosthenes, and then to perform binary search in the resulting array whenever we wanted to check if a number if prime. Here’s the c code:

#include <stdio.h>
#include <stdlib.h>

#define LIMIT 10000000 /*size of integers array*/
#define PRIMES 700000 /*size of primes array*/

int bSearch(int n,int array[], int start, int end){
    int middle = (start+end)/2;

    if (start>end)
        return 0;

    if (n==array[middle])
        return 1;

    if (n>array[middle])
        return bSearch(n,array,middle+1, end);
    else
        return bSearch(n,array,start,middle-1);
}

int main(){
    int i,j;
    int *primes,*numbers;
    int count = 0;

    primes = malloc(sizeof(int)*PRIMES);
    numbers = malloc(sizeof(int)*LIMIT);

    /*fill the array with natural numbers*/
    for (i=0;i<LIMIT;i++){
        numbers[i]=i+2;
    }

    /*sieve the non-primes*/
    for (i=0;i<LIMIT;i++){
        if (numbers[i]!=-1){
            for (j=2*numbers[i]-2;j<LIMIT;j+=numbers[i])
                numbers[j]=-1;
        }
    }

    /*transfer the primes to their own array*/
    j = 0;
    for (i=0;i<LIMIT&&j<PRIMES;i++)
        if (numbers[i]!=-1)
            primes[j++] = numbers[i];

    for (i=2;i<10000000;i++)
        if (bSearch(i,primes,0,j-1))
            count++;

    printf("count=%dn",count);

 return 0;
}

This is better than previous approach, but will use extra space.


Other good approaches
If you want an actual algorithm for making your own primes, Wikipedia has all sorts of good stuff on primes here, including links to the various methods for doing it, and prime testing here, both probability-based and fast-deterministic methods.

Probabilistic tests
That is, you carry out some tests and determine with some degree of certainty whether or not it’s prime. Some of probabilistic tests are :

• Fermat’s Primality Test
• Miller-Rabin test 
• Solovay-Strassen primality test

Some good primality test algorithms.

• AKS primality test (developed in IIT Kanpur)
• Fermat primality test
• Lucas-Lehmer test
• Solovay-Strassen primality test
• Miller-Rabin primality test (may be the simplest one)

A probable prime is an integer which, by virtue of having passed a certain test, is considered to be probably prime. Probable primes which are in fact composite (such as Carmichael numbers) are called pseudoprimes.

In 2002, Indian scientists at IIT Kanpur discovered a new deterministic algorithm known as the AKS algorithm. The amount of time that this algorithm takes to check whether a number N is prime depends on a polynomial function of the number of digits of N (i.e. of the logarithm of N)


References -
wikipedia,
technicalypto,
stackoverflow - 1,2,
programminglogic

Thanks