Skip to main content

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.. :)

Comments

Popular posts from this blog

Kisah Nyata Seorang Anak Bernama Andoy dari Filipina

This post is in Bahasa.
Ada seorang anak kecil kelas 4 SD yang selalu mengucap syukur dalam keadaan apapun. Ia tinggal di suatu desa di Negara Filipina. Setiap hari untuk sampai ke sekolahnya ia harus berjalan kaki melintasi daerah yang tanahnya berbatu dan menyeberangi jalan raya yang berbahaya dimana banyak kendaraan yang melaju kencang. Setiap kali berhasil menyeberangi jalan raya tersebut, Andoy selalu mampir sebentar ke Gereja untuk berdoa. Tindakannya ini diamati oleh Pdt. Agaton. Karena merasa terharu dengan sikap Andoy yang lugu dan beriman tersebut. Suatu hari ketika Andoy hendak masuk ke Gereja Pdt. Agaton menyapanya.
Bpk. Pdt : "Selamat pagi Andoy, apa kabarmu? Apakah kamu akan ke sekolah?"
Andoy : "Ya, Bapa Pendeta!" balas Andoy sambil tersenyum.
Bpk.Pdt : "Mulai sekarang saya akan membantu dan menemani kamu menyeberangi jalan raya tersebut setiap kali kamu akan menyeberang.
Andoy : Terima kasih, Bapa Pendeta."
Bpk. Pdt : "sekarang apa yang aka…

Blue Light Filtering with f.lux

Light, one of the very important parts of human living support, has tremendous benefit for us. Light itself is composed of many different rays. One of the components of light, called as blue light, has been known to tamper with our circadian rhythm.

Blue light itself can come from a lot of sources, including the lamp inside your room. However, the source which gives the most impact on people are from electronic devices. In this technology era, it's very hard for us to run away from using electronic devices. Those devices, such as Laptops and Handphones, have tremendously improve our quality of life by making our life easier and more fun through a lot of applications and systems available. Unfortunately, blue light emitted through the screen of those devices can affect our quality of sleep. Some research even advised us not to use our phone a few hours before we are going to sleep to improve our sleep quality.

For tech-savvy people, getting away from devices, especially handphone, …

Needlefish Attack

Just recently, a news spread about a young lady, died due to attack of a Needle fish. The story began when she was having a vacation with her family at Tanjung Karang beach, Makassar, Indonesia. This unfortunate event happened on January 01, 2016.



Liena (39) was soaking her body near the shoreline, whilst suddenly a needlefish jump towards her face. She was not able to dodge because it was too sudden. The fish, known with its long sharp and spear like snout, pierced through her right eyelids. She was then screaming for help. Her husband's family was then run to help her. She was quite badly injured. The wound was so deep that it even pierced through the skull and caused her to vomit blood.

She was brought to the hospital by ambulance to Kabelota Donggala hospital. Nevertheless, the wound was so bad that she eventually could not make it. She passed away in that hospital and the corpse was brought back to Balaikota Palu.



It's highly advised that we are keep being careful when playi…