Tuesday, May 1, 2012

Faster Prime Number Checker Algorithm

Checking for prime number is actually a simple one, but can sometimes be very tricky for big number. Though there exists more powerful algorithm to check for prime number, here I want to show you one simple algorithm that is proved to be fast enough.


//
//  main.cpp
//  Prime Number Checker
//
//  Created by Handra on 5/1/12.
//  Copyright (c) 2012 Handra. All rights reserved.
//

#include <iostream>
#include <cmath>

using namespace std ;

/* Function prototype */
int isPrime ( int number ) ;

int main ( int argc , const char * argv [ ] )
{
    int number = 12 ;
    
    cout << "Is Prime: " << isPrime ( number ) << endl ;
    
    return 0 ;
}

int isPrime ( int number )
{
    /* Every number below 2 is not prime */
    if ( number < 2 )
        return 0 ;
    
    /* Calculating the limit for denominator */
    int limit = ( int ) sqrt ( number ) ;
    
    /* Start the denominator from 2. We know that every number divided by 1 must have 0 carrier */
    for ( int i = 2 ; i <= limit ; i ++ )
        if ( number % i == 0 )
            return 0 ;
    
    return 1 ;
}

The above code is written using C++. Of course you can implement it using any other programming language.


So, as you can see within the function "isPrime", we first check whether the number is less than 2 or not. We know, by common sense and definition, that numbers below 2 are not considered as prime. Hence, we check that if the number is less that 2, then return 0, or false.


If the number is 2 or higher, then we need to check for it's primeness. First of all, we need to calculate the limit of the number we should use to divide the to-check-for-primeness-number. From the mathematical theorem, we know that the maximum factor value, that is not the same with the number, is the square root of the number. Proving of this theorem is beyond this post though. In C++, we use function sqrt that is defined in header cmath.


After that, the rest we need to do is loop starting from 2 to the limit to check whether there is another factor (besides 1 and the number itself). If any is found, then just return 0 (false) since there should be no other factor within 2 and the limit (inclusive). Otherwise, return 1 (true).


Hope this helps and happy coding.. :)

No comments:

Post a Comment