Algoritma dan Program Menentukan Bilangan Prima

Kaidah:
Bilangan prima adalah bilangan yang hanya memiliki dua faktor, yakni angka 1 dan bilangan itu sendiri.
Misalnya, angka 7 adalah bilangan prima karena hanya memiliki faktor 1 dan 7 (1x7 dan 7x1).
Sedangkan angka 9 bukan merupakan bilangan prima karena memiliki faktor 1, 3, 9 (1x9, 3x3, 9x1).
Angka 0 dan 1 bukan bilangan prima.
Angka 2 adalah satu-satunya bilangan genap bukan nol yang merupakan bilangan prima.


Penjelasan:
Untuk menentukan berapa banyak faktor yang dimiliki suatu bilangan, biasanya digunakan perulangan (repetition) mulai angka 1 sampai bilangan tersebut dan menguji tiap-tiap item apakah habis dibagi item tersebut. Jika habis, maka jumlah faktor bertambah.
Terakhir, diuji apakah jumlah faktor = 2. Jika ya, maka termasuk bilangan prima. Jika tidak, maka bukan termasuk bilangan prima.

Langkah ini bisa sangat panjang. Oleh karena itu perlu dilakukan pengujian pada tiap-tiap item apakah faktor > 2. Jika ya, maka looping berhenti.

Kita masih bisa mempersingkat langkah ini dengan cara membatasi perulangan. Jadi, perulangannya bukan sampai bilangan tersebut tetapi hanya sampai akar bilangannya saja. Misalnya, untuk menentukan apakah 101 termasuk bilangan prima atau tidak, kita tidak perlu melakukan perulangan sampai 101 kali tapi cukup 10 kali saja (akar 101 adalah 10.0498 dibulatkan ke bawah menjadi 10).


Implementasi Algoritma:
Dari penjelasan di atas dapat dibuat algoritma sebagai berikut,
1) Masukkan sebuah bilangan, simpan dengan nama "bilangan"
2) Tentukan limit yakni akar dari bilangan kemudian ambil bilangan bulatnya
3) Beri nilai awal 1 pada is_prime
4) Masukkan nilai a = 2
5) Jika bilangan habis dibagi a maka ubah is_prime menjadi 0
6) Jika is_prime bernilai 0 maka akhiri perulangan (menuju langkah 7). Jika tidak, maka ulangi ke langkah 5
7) Jika is_prime bernilai 1 dan bilangan bernilai lebih dari atau sama denga 2, maka katakan "termasuk bilangan prima". Jika tidak, katakan "bukan bilangan prima"
8) Selesai


Implementasi dalam Bahasa Java:

// nama file: Prima.java

import java.util.Scanner;

public class Prima {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int number;
        System.out.print("Masukkan sebuah bilangan: ");
        number = scanner.nextInt();
        boolean is_prime = true;
        double limit = Math.ceil(Math.sqrt(number));

        for (int i = 2; i <= limit; i++) {
            if (number % i == 0) {
                is_prime = false;
                break;
            }
        }

        if (is_prime) {
            System.out.println(number + " adalah bilangan prima");
        } else {
            System.out.println(number + " bukan bilangan prima");
        }
    }
}

Implementasi dalam Bahasa C:

#include <stdio.h>
#include <math.h>

int main() {
    int bilangan;
    printf("Masukkan sebuah bilangan: ");
    scanf("%d", &bilangan);

    int limit = floor(sqrt(bilangan));
    int is_prime = 1;

    int a;
    for (a=2; a<=limit; a++) {
        if (bilangan % a == 0) {
            is_prime = 0;
            break;
         }
    }

    if (is_prime && bilangan >=2) {
        printf("%d termasuk bilangan prima\n", bilangan);
    } else {
        printf("%d bukan bilangan prima\n", bilangan);
    }

    return 0;
}