Java Programming : Mengecek Bilangan Prima

Assalamu'alaikum.
Pagi.. Kali ini postingannya membahas masalah yang tingkatnya sedikit diatas dasar.
Problem case yang akan dibawa kali ini adalah bagaimana caranya mengecek apakah suatu bilangan itu prima atau bukan.

Kalo dipikir secara logika sih, artinya kan bilangan prima itu bilangan yang bisa habis dibagi hanya oleh dirinya sendiri atau angka 1.
Yang artinya jika coba dibagi dengan bilangan lain selain itu, pasti akan menghasilkan sisa pembagian bukan 0, atau tidak habis dibagi.

Logika yang dipakai disini hampir mirip dengan konsep diatas, hanya saja lebih di persingkat sedikit.
Pertama-tama lihat source code dibawah ini dulu.

import java.util.Scanner;

public class CheckPrime
{
   public static void main(String[] args){
       Scanner input = new Scanner(System.in);
       int prime, i;
       double root;
       boolean error = false;
      
       System.out.println("Program Untuk Mengecek Bilangan Prima atau Bukan");
       System.out.println("------------------------------------------------");
       System.out.println("Masukkan Bilangan >> ");
      
       prime = input.nextInt();
       root = Math.sqrt(prime);
      
       for(i = 2; i <= root; i++){
           if(prime % i == 0){
               //System.out.println("Cek disini");  //Instruksi ini hanya menunjukkan apabila pada percabangan ini hanya dilakukan sekali saja penjalanan
               error = true;
               break;
           }
       }
      
       System.out.println("");
       if(error){
           System.out.println("Bilangan " + prime + " bukan Bilangan Prima");
       }
       else{
           System.out.println("Bilangan " + prime + " adalah Bilangan Prima");
       }
   }
}

Dari source code diatas, ada yang merasa ganjal ga?
Biasanya orang akan berpikir untuk membagi suatu bilangan sampai setengah kali bilangan tersebut.
Misal : Jika bilangan yang dimasukkan adalah 50. Maka batas dibaginya cukup sampai 25 saja, karena 50 / 26 atau 50 / 27, dst tidak akan habis dibagi, kecuali oleh 50 sendiri.
Cara itu sebenarnya sudah efektif. Tapi ada cara yang lebih efektif lagi.

Misal : Jika bilangan yang dimasukkan adalah 50.
Maka pengecekan cukup sampai square root / akar dari 50, dalam hal ini akar dari 50 bernilai 7,1..
Karena ketika 50 / 2 = 25 (habis dibagi)
50 / 5 = 10 (habis dibagi)
Nah, sejatinya 50 tidak perlu di cek dengan angka 10 ataupun 25 lagi, karena jika 50 / 10 akan menghasilkan 5, dan jika dibagi 25 akan menghasilkan 2.
Hal tersebut hanyalah membolak-balik pembagian saja. Sehingga batasan yang lebih pendek adalah sampai nilai akar dari bilangan tersebut.

Untuk contoh pengeksekusian programnya bisa dilihat di bawah.


Postingan selanjutnya mungkin membahas yang sedikit lebih susah dibandingkan problem ini.
Jadi untuk postingan yang ini cukup sekian dulu.
Dan seperti biasanya, jika ada pertanyaan atau saran untuk post ini, silahkan tulis di komentar. Terima kasih.
Wassalamu'alaikum.