Mengecek Bilangan Prima

Bilangan prima adalah bilangan yang habis dibagi oleh 1 dan bilangan itu sendiri.

Ada banyak cara untuk mengecek apakah suatu bilangan prima atau bukan. Berikut ini merupakan algoritma yang sering kita jumpai.
1. Bilangan x dibagi 2, 3, 4, ..., sampai x/2

Kekurangan dari algoritma di atas ialah prosesnya sangat lambat dan tidak efektif untuk bilangan yang besar.

Solusinya, gunakan algortima berikut ini.
1. Bilangan x dicek apakah kurang dari 2 atau merupakan bilangan kelipatan 2.
2. Jika ya, maka bukan bilangan prima.
3. Jika tidak, maka bilangan x dibagi 3, 5, 7, ..., sampai akar dari x.

Algoritma ini sangat efektif untuk mengecek bilangan yang sangat besar. Misalnya, 2147483647. Bilangan tersebut merupakan batas atas dalam variabel signed integer. Untuk mengecek bilangan tersebut, biasanya program membutuhkan waktu beberapa detik. Namun, jika menggunakan algoritma ini, pengecekan bisa selesai dalam seketika.

Berikut implementasinya dalam bahasa C.

// Cek Bilangan Prima
#include<stdio.h>
#include<math.h>

int main()
{    int N, akar, i;
    scanf("%d", &N);

    if(N < 2 || N % 2 == 0)
    {    printf("Bukan bilangan prima");
        return 0;
    }

    akar = sqrt(N);
    for(i = 3; i <= akar; i+=2)
        if(N % i == 0)
        {    printf("Bukan bilangan prima");
            return 0;
        }
       
    printf("Bilangan prima");
}

Contoh input:
2147483647

Output:
Bilangan prima