4 Algoritma Mencari Bilangan Prima beserta Flowchart dan Contoh Programnya

Sumber ilustrasi: Pinterest

Sebagai seorang programmer, penting untuk memahami tentang bilangan prima. Memahami bilangan prima dan sifat-sifatnya dapat membantu dalam mengembangkan algoritma yang lebih efisien, memecahkan masalah matematika, dan memahami algoritma kriptografi yang sering digunakan dalam keamanan data.

Definisi Bilangan Prima

Bilangan prima (Prime Number) adalah bilangan asli yang lebih besar dari 1 dan hanya memiliki dua pembagi yang berbeda, yaitu 1 dan dirinya sendiri. Bilangan-bilangan ini tidak dapat dibagi habis oleh bilangan lain kecuali oleh 1 dan bilangan itu sendiri.

Sifat-sifat yang menjadi ciri sebuah bilangan adalah prima disebut primalitas (Primality). Untuk mengecek apakah sebuah bilangan adalah prima diperlukan tes primalitas (Primality Test). Jika bilangan tersebut memiliki primalitas (memenuhi semua sifat bilangan prima) maka bilangan tersebut adalah prima.

Bilangan lebih dari satu yang tidak termasuk prima disebut komposit (Composite Number). Bilangan Komposit akan membentuk pola segi empat jika disusun, sedangkan bilangan prima tidak. Lihat ilustrasi di bawah!

4 Metode atau Algoritma Mencari Bilangan Prima

Saya memberikan tidak hanya satu metode agar Kamu tahu bahwa banyak metode mencari bilangan prima. 

Berikut beberapa metode untuk mencari bilangan prima :

1. Metode Brute Force

Metode Brute Force adalah pendekatan sederhana untuk mencari bilangan prima dengan menguji setiap bilangan secara berurutan untuk memeriksa apakah itu prima atau bukan.

Metode Brute Force lebih ditujukan untuk mengecek primalitas dari sebuah bilangan acak. Misal kita ingin mengecek apakah bilangan x adalah prima, lebih baik gunakan metode Brute Force.

Metode ini sederhana tetapi tidak efisien untuk mencari bilangan prima yang sangat besar karena memerlukan banyak pengujian. Kompleksitas waktu metode ini adalah O(n), di mana n adalah bilangan yang ingin diperiksa, yang berarti harus melakukan pengujian sebanyak bilangan tersebut.

Algoritma Brute Force sebagai berikut:

1. Tentukan bilangan yang ingin diuji.
2. Jika bilangan kurang dari atau sama dengan 1, bukan prima.
3. Uji apakah bilangan tersebut memiliki pembagi selain 1 dan dirinya sendiri.
4. Untuk menguji, lakukan :
   1. Iterasi semua bilangan dari 2 hingga bilangan - 1.
   2. Hitung sisa bagi dari bilangan yang diuji dengan bilangan iterasi.
   3. Jika terdapat satu saja bilangan iterasi yang membagi habis bilangan yang diuji, maka bukan prima.
   4. Tetapi jika tidak ada, maka bilangan tersebut prima.

Algoritma Brute Force dalam Pseudocode

fungsi isPrime(bilangan):
    jika bilangan <= 1:
        kembalikan false

    untuk setiap i dari 2 hingga bilangan - 1:
        jika bilangan mod i == 0:
            kembalikan false

    kembalikan true

Program Mencari Bilangan Prima dengan Algoritma Brute Force

Berikut saya menggunakan bahasa JavaScript untuk mengimplementasikan algoritma Brute Force.

function isPrime(number) {

    if (number <= 1) {

      return false;

    }

 

    for (let i = 2; i < number; i++) {

      if (number % i === 0) {

        return false;

      }

    }

 

    return true;

}

Penjelasan baris per baris:

1. function isPrime(number): Mendefinisikan fungsi isPrime yang menerima satu parameter number, yaitu bilangan yang akan diperiksa.
2. if (number <= 1) { return false; }: Pada baris ini, dilakukan pengecekan apakah number kurang dari atau sama dengan 1. Jika iya, maka bilangan tersebut bukanlah bilangan prima, sehingga fungsi mengembalikan false.
3. for (let i = 2; i < number; i++) {: Di sini, kita melakukan iterasi menggunakan variabel i dari 2 hingga bilangan sebelum number.
4. if (number % i === 0) { return false; }: Pada setiap iterasi, kita memeriksa apakah number dapat dibagi habis oleh i. Jika hasil sisa pembagian number % i adalah 0, itu berarti number memiliki faktor pembagi selain 1 dan dirinya sendiri. Oleh karena itu, fungsi mengembalikan false.
5. Jika program melewati semua iterasi tanpa melakukan return false, itu berarti number tidak dapat dibagi habis oleh bilangan lain selain 1 dan dirinya sendiri, sehingga bilangan tersebut adalah bilangan prima. Fungsi mengembalikan true.

Dengan demikian, fungsi isPrime ini dapat digunakan untuk memeriksa keprimaan suatu bilangan dalam program.

2. Metode Trial Division

Metode ini adalah pengembangan dari metode Brute Force. Algoritmanya sama, hanya saja metode ini membatasi pengecekan hanya sampai akar dari bilangan yang diuji.

Mencari primalitas dari bilangan 6 memang cepat, hanya perlu mengulangi pengujian sebanyak 6 kali. Namun bagaimana jika bilangannya 987.688 atau lebih banyak? Mengulangi pengecekan sebanyak itu akan memakan waktu dan sumber daya yang banyak.

Pengujian hanya perlu dilakukan sampai √ n. Mengapa demikian?

Baik, kita langsung ambil contoh. Misal n adalah 11.

Akar 11 adalah 3.31.

Kita lakukan pengujian dari 2 sampai kurang dari atau sama dengan 3.31.

11 % 2 = sisa 1.

11 % 3 = sisa 2.

Dengan hanya melakukan pengujian sampai akar dari 11, kita sudah tahu, bahwa tidak terdapat bilangan yang membagi habis 11.

Tidak perlu melanjutkan pengujian sampai 11 karena sudah pasti tidak ada yang bisa membagi habis bilangan 11.

Coba saja kita uji dengan bilangan 4.

11 % 4 = sisa 3.

4 adalah kelipatan 2. Sebelumnya sudah diuji dengan 2 dan tidak habis. Maka jika diuji dengan semua kelipatan 2, tidak akan habis.

Lalu, jika 11 dibagi 2, hasilnya adalah 5, maka 5 dan kelipatannya tidak akan membagi habis bilangan 11.

Kemudian, karena 3 tidak bisa membagi habis 11, maka 3 dan kelipatannya tidak bisa membagi habis 11.

Contoh kedua: misalkan n adalah 49.

Akar dari 49 adalah 7.

Jika akar kuadrat dari suatu bilangan adalah bilangan bulat, maka berarti bilangan tersebut dapat dibagi habis oleh akar kuadratnya. Jadi jika suatu bilangan memiliki akar kuadrat yang merupakan bilangan bulat, sudah pasti bukan bilangan prima tanpa perlu mencari faktor pembagi yang lain.

Tapi tidak setiap bilangan yang memiliki akar kuadrat desimal adalah prima. Perlu pengujian lanjut untuk mengetahuinya.

Algoritma Trial Division dalam Pseudocode

fungsi isPrime(bilangan):
    jika bilangan <= 1:
        kembalikan false

    untuk setiap i dari 2 hingga kurang dari sama dengan akar bilangan:
        jika bilangan mod i == 0:
            kembalikan false

    kembalikan true

Program Mencari Bilangan Prima dengan Algoritma Trial Division

Berikut adalah contoh program menggunakan metode trial division untuk mencari bilangan prima dalam JavaScript:

function isPrime(number) {

    if (number <= 1) {

      return false;

    }

 

    for (let i = 2; i <= Math.sqrt(number); i++) {

      if (number % i === 0) {

        return false;

      }

    }

 

    return true;

}

JavaScript mempunya metode bawaan untuk menghitung akar kuadrat bilangan yaitu Math.sqrt().

Beberapa bahasa pemrograman yang mendukung operasi matematika seperti: Phyton; PHP; Java; C/C++; Ruby; dan Kotlin; memiliki metode bawaan untuk menghitung akar kuadrat.

3. Metode Perulangan Terbalik

Terpikir di benak saya untuk membuat perulangan terbalik dalam pengujian primalitas. Dimulai dari akar kuadrat bilangan sampai lebih dari sama dengan 2.

Perulangan terbalik ini akan membuat pengujian lebih efektif untuk beberapa kasus.

Sebagai contoh:

Misalkan n adalah 49 dan memiliki akar kuadrat bilangan bulat 7.

Setiap bilangan yang memiliki akar kuadrat berupa bilangan bulat maka dia adalah komposit, bukan prima.

4 bukan prima, akar 4 adalah bilangan bulat 2. 9 bukan prima, akar kuadratnya adalah 3.

Dalam hal ini, jika akar kuadrat bilangan adalah bilangan bulat, perulangan terbalik hanya akan membuat pengujian satu kali putaran. Karena dimulai dari akar kuadrat bilangan tersebut yang sudah pasti menghasilkan `false` ketika bilangan dimodulus dengan akar kuadrat pada putaran pertama.

Pada putaran pertama, n adalah 49 dan i sama dengan 7 (akar n). Maka hanya dengan putaran pertama hasil sudah ditentukan, 49 % 7 adalah 0, maka false, bukan prima.

Berikut kode program JavaScript Metode Perulangan Terbalik.

function isPrime(number) {

    if (number <= 1) {

      return false;

    }

 

    for (let i = Math.sqrt(number); i >= 2; i--) {

      console.log("Loop!")

      if (number % i === 0) {

        return false;

      }

    }

 

    return true;

}

Lihat perbandingannya!

Perulangan Terbalik (kiri) memerlukan satu kali loop.

Dengan ini, pengujian akan dilakukan dengan lebih cepat untuk kasus akar bilangan berupa bilangan bulat.

4. Metode Sieve of Eratosthenes

Metode Sieve of Eratosthenes adalah metode yang lebih efisien untuk mencari semua bilangan prima hingga batas yang diberikan. 

Algoritma Sieve of Eratosthenes: 

1. Buatlah sebuah array atau list berukuran n, di mana n adalah batas yang ditentukan.
2. Inisialisasi semua elemen array dengan nilai true, menandakan bahwa semua bilangan pada awalnya dianggap sebagai bilangan prima.
3. Ubah nilai array di index 0 dan 1 menjadi false, karena 0 dan 1 bukan prima. 
4. Mulailah dengan bilangan pertama, yaitu 2, dan tandai semua kelipatan 2 sebagai non-prima dengan mengubah nilainya menjadi false.
5. Lanjutkan ke bilangan berikutnya yang belum ditandai (bilangan prima), yaitu 3, dan tandai semua kelipatan 3 sebagai non-prima.
6. Lakukan proses ini untuk semua bilangan prima berikutnya yang belum ditandai, hingga mencapai akar kuadrat dari n.
7. Setelah itu, semua bilangan yang masih memiliki nilai true di array adalah bilangan prima.

Metode Sieve of Eratosthenes lebih efisien daripada metode Brute Force karena hanya melakukan pengujian pada bilangan-bilangan yang relevan. Metode Sieve of Eratosthenes umumnya lebih disukai untuk mencari bilangan prima karena kinerjanya yang lebih baik. 

Namun, jika Anda hanya perlu mencari satu atau beberapa bilangan prima secara acak, metode Trial Division adalah pilihan terbaik. 

Program JavaScript metode Sieve of Eratosthenes:

function sieveOfEratosthenes(batas) {

    // Inisialisasi array boolean dengan nilai true

    // yang menandakan bahwa bilangan tersebut masih prima

    let primes = new Array(batas + 1).fill(true);

   

    // 0 dan 1 bukan bilangan prima, setel nilainya menjadi false

    primes[0] = false;

    primes[1] = false;

   

    // Mulai dari bilangan 2, iterasi hingga akar dari n

    for (let i = 2; i <= Math.sqrt(batas); i++) {

      // Jika bilangan tersebut masih dianggap prima

      if (primes[i] === true) {

        // Tandai semua kelipatan bilangan tersebut sebagai bukan prima

        for (let j = i * i; j <= batas; j += i) {

          primes[j] = false;

        }

      }

    }

   

    // Mengumpulkan semua bilangan prima dalam array

    let primeNumbers = [];

    for (let i = 2; i <= batas; i++) {

      if (primes[i] === true) {

        primeNumbers.push(i);

      }

    }

   

    return primeNumbers;

  }

 

  // Contoh penggunaan

  let batas = 50;

  let primes = sieveOfEratosthenes(batas);

  console.log(`Bilangan prima antara 1 dan ${batas}:`);

  console.log(primes);

Penjelasan:

1. Fungsi sieveOfEratosthenes(batas) menerima parameter batas yang merupakan batas atas rentang bilangan yang akan diperiksa.
2. Array primes digunakan untuk menyimpan status keprimaan dari setiap bilangan dari 0 hingga batas.
3. Nilai awal semua elemen array primes diatur sebagai true untuk menandakan bahwa semua bilangan masih dianggap prima.
4. Elemen dengan indeks 0 dan 1 diubah menjadi false karena bukan bilangan prima.
5. Iterasi dimulai dari bilangan 2 hingga akar kuadrat dari batas.
6. Jika suatu bilangan i masih dianggap prima, maka semua kelipatan bilangan i yang lebih besar dari i * i akan ditandai sebagai bukan prima dengan mengubah nilainya menjadi false.
7. Setelah selesai iterasi, array primes akan berisi status keprimaan dari semua bilangan dalam rentang yang ditentukan.
8. Selanjutnya, bilangan prima dikumpulkan dalam array primeNumbers dengan memeriksa nilai true dalam array primes.
9. Akhirnya, array primeNumbers berisi semua bilangan prima dalam rentang yang ditentukan, dan akan dicetak di konsol.

Contoh di atas akan mencetak bilangan prima antara 1 dan 50. Anda dapat mengubah nilai n sesuai dengan kebutuhan Anda untuk mencari bilangan prima dalam rentang yang berbeda. 

Flowchart Menentukan Bilangan Prima dengan Metode Trial Division

Saya pilih metode Trial Division untuk dibuat flowchart dibanding Brute Force karena keduanya memiliki algoritma yang sama, namun Trial Division lebih efektif. 

Berikut Flowchart Bilangan Prima Trial Division: 

Unduh Master File (Buka dengan app.diagrams.net)

Flowchart Deret Bilangan Prima dengan Metode Sieve of Eratosthenes

Metode Sieve of Eratosthenes memiliki efektivitas terbaik untuk mencari deretan bilangan prima sampai batas tertentu. Untuk itu saya memilih ini untuk dibuat Flowchart Deret Bilangan Prima. Walau metode yang lain pun bisa untuk mencari deret bilangan prima. 

Berikut Flowchart Mencari Deret Bilangan Prima: 

Unduh Master File (Buka dengan app.diagrams.net)