Periksa Jika Nomor Adalah Perdana di Jawa

1. Perkenalan

Pertama, mari kita bahas beberapa teori dasar.

Sederhananya, sebuah bilangan adalah bilangan prima jika hanya habis dibagi satu dan oleh bilangan itu sendiri. Bilangan non-prima disebut bilangan komposit. Dan nomor satu bukanlah bilangan prima atau komposit.

Pada artikel ini, kita akan melihat berbagai cara untuk memeriksa primalitas angka di Java.

2. Penerapan Kustom

Dengan pendekatan ini, kita dapat memeriksa apakah sebuah bilangan antara 2 dan (akar kuadrat dari bilangan tersebut) dapat secara akurat membagi bilangan tersebut.

Logika berikut akan mengembalikan nilai benar jika bilangan tersebut adalah bilangan prima:

public boolean isPrime(int number) { return number > 1 && IntStream.rangeClosed(2, (int) Math.sqrt(number)) .noneMatch(n -> (number % n == 0)); }

3. Menggunakan BigInteger

Kelas BigInteger umumnya digunakan untuk menyimpan bilangan bulat berukuran besar, yaitu yang lebih besar dari 64bits. Ini menyediakan beberapa API yang berguna untuk bekerja dengan nilai int dan long .

Salah satu API tersebut adalah isProbablePrime . API ini mengembalikan nilai salah jika bilangan tersebut pasti merupakan gabungan dan mengembalikan nilai benar jika ada kemungkinan bilangan tersebut menjadi bilangan prima. Ini berguna ketika berhadapan dengan bilangan bulat besar karena ini bisa menjadi komputasi yang cukup intensif untuk memverifikasi ini sepenuhnya.

Catatan singkat - API isProbablePrime menggunakan apa yang dikenal sebagai tes primalitas “Miller - Rabin dan Lucas - Lehmer” untuk memeriksa apakah bilangan tersebut mungkin bilangan prima. Dalam kasus di mana jumlahnya kurang dari 100 bit, hanya pengujian "Miller - Rabin" yang digunakan, jika tidak, kedua pengujian digunakan untuk memeriksa keutamaan sebuah angka.

Uji “Miller-Rabin” mengulang beberapa kali untuk menentukan primalitas bilangan dan jumlah iterasi ini ditentukan oleh pemeriksaan sederhana yang melibatkan panjang bit nomor dan nilai kepastian yang diteruskan ke API:

public boolean isPrime(int number) { BigInteger bigInt = BigInteger.valueOf(number); return bigInt.isProbablePrime(100); }

4. Menggunakan Apache Commons Math

Apache Commons Math API menyediakan metode bernama org.apache.commons.math3.primes.Primes, yang akan kita gunakan untuk memeriksa keutamaan sebuah angka.

Pertama, kita perlu mengimpor pustaka Apache Commons Math dengan menambahkan ketergantungan berikut di pom.xml kita :

 org.apache.commons commons-math3 3.6.1 

Versi terbaru dari commons-math3 dapat ditemukan di sini.

Kita bisa melakukan pemeriksaan hanya dengan memanggil metode ini:

Primes.isPrime(number);

5. Kesimpulan

Dalam artikel singkat ini, kami telah melihat tiga cara untuk memeriksa keutamaan nomor tersebut.

Kode untuk ini dapat ditemukan di paket com.baeldung.algorithms.primechecker di Github.