Temukan Jika Dua Angka Relatif Prima di Jawa

1. Ikhtisar

Diketahui dua bilangan bulat, a dan b , kita mengatakan bahwa keduanya relatif prima jika satu-satunya faktor yang membagi keduanya adalah 1. Saling prima atau koprime adalah sinonim untuk bilangan prima yang relatif.

Dalam tutorial singkat ini, kami akan menjelaskan solusi untuk masalah ini menggunakan Java.

2. Algoritma Faktor Umum Terbesar

Ternyata, jika pembagi persekutuan terbesar ( gcd ) dari 2 bilangan a dan b adalah 1 (yaitu gcd (a, b) = 1 ) maka a dan b relatif prima. Akibatnya, menentukan apakah dua bilangan relatif prima terdiri dari mencari jika gcd adalah 1.

3. Implementasi Algoritma Euclidean

Di bagian ini, kita akan menggunakan algoritma Euclidean untuk menghitung gcd dari 2 angka.

Sebelum kita menunjukkan implementasi kita, mari kita rangkum algoritme dan lihat contoh singkat bagaimana menerapkannya demi pemahaman.

Jadi, bayangkan kita memiliki dua bilangan bulat, a dan b . Dalam pendekatan berulang, pertama kita membagi a dengan b dan mendapatkan sisanya. Berikutnya, kita menetapkan suatu nilai b , dan kami menetapkan b nilai sisa. Kami ulangi proses ini sampai b = 0 . Akhirnya, ketika kita mencapai titik ini, kita mengembalikan nilai a sebagai hasil gcd , dan jika a = 1 , kita dapat mengatakan bahwa a dan b relatif prima.

Mari kita coba pada dua bilangan bulat, a = 81 dan b = 35 .

Dalam hal ini, sisa dari 81 dan 35 (81% 35) adalah 11 . Jadi, pada langkah iterasi pertama, kita akhiri dengan a = 35 dan b = 11 . Akibatnya, kami akan melakukan iterasi lain.

Sisa dari 35 dibagi 11 adalah 2 . Akibatnya, kita sekarang memiliki a = 11 (kita menukar nilai) dan b = 2 . Ayo lanjutkan.

Satu langkah lagi akan menghasilkan a = 2 dan b = 1 . Sekarang, kita mendekati akhir.

Terakhir, setelah satu iterasi lagi, kita akan mencapai a = 1 dan b = 0 . Algoritme mengembalikan 1 dan kita dapat menyimpulkan bahwa 81 dan 35 memang relatif prima.

3.1. Implementasi Imperatif

Pertama, mari kita implementasikan versi Java imperatif dari algoritma Euclidean seperti yang dijelaskan di atas:

int iterativeGCD(int a, int b) { int tmp; while (b != 0) { if (a < b) { tmp = a; a = b; b = tmp; } tmp = b; b = a % b; a = tmp; } return a; } 

Seperti yang dapat kita perhatikan, dalam kasus di mana a kurang dari b , kita menukar nilai sebelum melanjutkan. Algoritma berhenti ketika b adalah 0.

3.2. Implementasi Rekursif

Selanjutnya, mari kita lihat implementasi rekursif. Ini mungkin lebih bersih karena menghindari pertukaran nilai variabel eksplisit:

int recursiveGCD(int a, int b) { if (b == 0) { return a; } if (a < b) { return recursiveGCD(b, a); } return recursiveGCD(b, a % b); } 

4. Menggunakan Implementasi BigInteger

Tapi tunggu - bukankah algoritma gcd sudah diterapkan di Java? Ya itu! Kelas BigInteger menyediakan metode gcd yang mengimplementasikan algoritma Euclidean untuk menemukan pembagi persekutuan terbesar.

Dengan menggunakan metode ini, kita dapat lebih mudah menyusun algoritme yang relatif prima seperti:

boolean bigIntegerRelativelyPrime(int a, int b) { return BigInteger.valueOf(a).gcd(BigInteger.valueOf(b)).equals(BigInteger.ONE); } 

5. Kesimpulan

Dalam tutorial singkat ini, kami telah menyajikan solusi untuk masalah menemukan jika dua bilangan relatif prima menggunakan tiga implementasi algoritma gcd .

Dan, seperti biasa, kode sampel tersedia di GitHub.