Monday, February 27, 2012

Fastest way of calculating Prime Number with less system overhead with C code.

A number is said to be a prime number if it is divisible only by 1 and  the number itself. That is prime number is divisible by exactly two numbers. For example, 11 is prime number because it is divisible by 1 and 11 itself  but 4 is not prime number because it is divisible by 1, 2 and 4.
Test of prime number is famous question in programming. You are supplied any arbitrary number and you have to find out whether it is prime or not. There are various methods and algorithms for testing the prime number condition. Some methods take less iteration and in turn less overhead and some  methods take large iteration and in turn large overhead. I will present you two methods; one uses large number of iterations and another uses drastically reduced number of iterations.
First method (High Iterations, Slow process)

In this method, a number to be tested is divided by successive numbers between 2 and the number itself. If the number is exactly divided by any one of the number between the range, then it is said to be not prime and if it is exactly divided by the number itself but not any other numbers then it is said to be prime number. Let’s take an example of 11. 11  is divided by numbers starting from 2 to 11. But it is not exactly divided by any other numbers except 11. So 11 is said to be prime number. So to check 11, a program must loops 9 times.If the number to be tested is very high then number of loop also becomes very high. A C code for this method is
int isPrime(int n){
    int i = 2, result;
    do{
        result = n%i;
        if(result == 0) break;
        i++;
    }while(n != i);
    if(n == i) return 1;
    else return 0;
} 

Second method (Low Iterations, Fast process)
In this method, the loop is iterated from 3 to the square root of the number but not up to the number in step of 2. For example to check 23, the loop is iterated from 3 to sqrt(23) i.e up to 4 in step of 2. Since 23 is not exactly divided by 3, it is prime number. Similarly to check 25,the loop is from 3 to sqrt(25) = 5 in step of 2(i.e by 3 and 5), but it is exactly divided by 5, so it is not prime number. A C code for this method is
int isPrime(int n) { 
    int i;
    if(n == 2) return 1;
    if(n%2 == 0) return 0;
    for(i = 3; i*i<=n; i+=2) {
        if(n%i == 0) return 0;
    }
    return 1;
} 

No comments:

Post a Comment