Bilangan Prima Java: Menemukan dan Memeriksa Keunikannya

Soal klasik yang hampir selalu muncul pas latihan atau interview kerja: cek apakah sebuah angka bilangan prima, pakai Java. Kelihatannya sepele, tapi justru di sini kita bisa lihat perjalanan sebuah kode dari versi “jalan saja” sampai versi yang benar-benar efisien.

Sebelum ke kode, ingat dulu definisinya: bilangan prima adalah bilangan bulat positif lebih besar dari 1 yang cuma punya dua pembagi - 1 dan dirinya sendiri. Jadi 2, 3, 5, 7, 11 masuk daftar; sedangkan 4 gugur karena bisa dibagi 2. Perhatikan juga 2 itu prima genap satu-satunya, fakta kecil yang sering keluar sebagai soal jebakan 🙂

Cara paling dasar: brute force

Logikanya lugas: coba bagi bilangannya dengan semua angka mulai 2 sampai number - 1. Kalau ada yang habis dibagi, dia bukan prima.

public class PrimeNumberChecker {
    public static boolean isPrime(int number) {
        if (number <= 1) {
            return false;
        }
        for (int i = 2; i < number; i++) {
            if (number % i == 0) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        int numToCheck = 17;
        if (isPrime(numToCheck)) {
            System.out.println(numToCheck + " adalah bilangan prima.");
        } else {
            System.out.println(numToCheck + " bukan bilangan prima.");
        }
    }
}

Output:

17 adalah bilangan prima.

Beberapa hal yang perlu dicermati dari kode di atas:

1. Penjagaan number <= 1 wajib ada, karena 0 dan 1 bukan prima menurut definisi (prima harus punya tepat dua pembagi).
2. Operator % adalah sisa bagi - kalau number % i == 0 artinya i berhasil membagi rata, jadi number pasti bukan prima.
3. Loop-nya langsung return false begitu ketemu pembagi pertama. Tidak usah lanjut, hemat waktu.

Versi ini benar, tapi boros. Untuk mengecek 1 juta, loop-nya muter hampir sejuta kali. Padahal…

Optimasi: cukup cek sampai akar kuadrat

Ini trik matematika yang bikin kode jauh lebih cepet. Jika n = a × b, salah satunya pasti ≤ √n. Artinya kalau n punya pembagi selain 1 dan dirinya, pasti ketemu sebelum akar kuadratnya. Membuang waktu mengecek setelah titik itu = percuma.

public static boolean isPrime(int number) {
    if (number <= 1) {
        return false;
    }
    if (number == 2) {
        return true;
    }
    if (number % 2 == 0) {
        return false;
    }
    for (int i = 3; i * i <= number; i += 2) {
        if (number % i == 0) {
            return false;
        }
    }
    return true;
}

Ada tiga lapis penghematan di sini:

1. i * i <= number menggantikan Math.sqrt() - tanpa panggilan fungsi ekstra, dan aman dari masalah pembulatan desimal.
2. Bilangan genap ditangkap duluan lewat number % 2 == 0, sehingga loop tinggal menguji pembagi ganjil (i += 2). Setengah pekerjaan hilang begitu saja.
3. Kasus 2 ditangani eksplisit supaya prima genap satu-satunya itu tidak ikut tersingkir.

Untuk bilangan besar bedanya nyata: mengecek 10.000 versi brute force butuh ~10.000 iterasi, versi ini cuma ~50.

Mencari banyak prima sekaligus: Sieve of Eratosthenes

Kalau kebutuhannya bukan mengecek satu angka tapi menampilkan semua prima dalam rentang, mengeceknya satu-satu itu boros. Algoritma Sieve of Eratosthenes (saringan Eratosthenes, nama orang Yunani kuno) bekerja dengan cara kebalikan: mulai dari daftar semua angka, lalu coret kelipatannya satu per satu.

import java.util.Arrays;

public class PrimeSieve {
    public static void main(String[] args) {
        int n = 30;
        boolean[] isPrime = new boolean[n + 1];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;

        for (int i = 2; i * i <= n; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= n; j += i) {
                    isPrime[j] = false;
                }
            }
        }

        System.out.println("Bilangan prima antara 1 dan " + n + " adalah:");
        for (int i = 2; i <= n; i++) {
            if (isPrime[i]) {
                System.out.print(i + " ");
            }
        }
    }
}

Output:

Bilangan prima antara 1 dan 30 adalah:
2 3 5 7 11 13 17 19 23 29 

Cara bacanya: array isPrime awalnya menandai semua angka sebagai prima (true). Lalu untuk tiap angka yang masih bertahan, semua kelipatannya dicoret. Coret kelipatan 2, kelipatan 3, kelipatan 5, dst - sisanya otomatis prima. Detail cerdasnya: coretan mulai dari i * i, bukan i * 2, karena kelipatan yang lebih kecil sudah tercoret oleh prima sebelumnya.

Ke mana lanjutannya

Dua algoritma di atas sudah cukup untuk 99% kasus sehari-hari. Untuk bilangan super besar (misalnya dunia kriptografi yang main di ratusan digit), digunakan algoritma lain seperti Miller-Rabin probabilistic test atau Segmented Sieve. Menariknya, keamanan HTTPS yang kalian pakai tiap hari justru bersandar pada sulitnya memfaktorkan bilangan hasil perkalian dua prima raksasa - jadi konsep “sepele” ini ternyata fondasi keamanan internet.

• Algoritma Bilangan Prima di Python dan C++
• Contoh Program Java Menampilkan Bilangan Ganjil dan Genap
• Contoh Program Binary Tree pada Java
• Polimorfisme di Java

Kesimpulan

Mengecek bilangan prima di Java dimulai dari definisi sederhana: hanya punya pembagi 1 dan dirinya sendiri. Versi brute force menguji semua pembagi dari 2 sampai n-1; versi optimal cukup sampai √n dengan langkah ganjil saja. Untuk menemukan banyak prima sekaligus, Sieve of Eratosthenes jauh lebih efisien dengan teknik menyaring kelipatan. Dari soal latihan yang tampak sederhana ini, kalian justru belajar pola optimasi yang kepakai di banyak algoritma lain.