Pada video ini kita akan mengerjakan latihan lagi, kali ini kita akan menuliskan kode untuk algoritma Sieve of Eratosthenes.

Sieve of Eratosthenes ini adalah algoritma yang paling cepat untuk mencari bilangan prima. Jadi latihan kali ini masih berkaitan dengan latihan sebelumnya ya. Teman-teman bisa menggunakan source code latihan terakhir sebagai kode dasar untuk mengerjakan latihan. Kita lihat dahulu bagaimana cara kerja algoritma untuk mencari bilangan prima diantara 1 hingga 50. Kita siapkan dahulu tabel yang berisi angka 1 hingga 50 dan kita anggap semuanya adalah bilangan prima.

Pertama kita coret dahulu angka 1, karena ada aturan pengecualian bahwa angka 0 dan 1 tidak termasuk bilangan prima.

Kita mulai memeriksa dari angka 2. Apabila angka 2 pada tabel belum dicoret, artinya 2 adalah bilangan prima. Kemudian berhubung 2 adalah bilangan prima, maka kita harus mencoret semua kelipatan 2 pada tabel.

Kita lanjutkan pemeriksaan ke angka berikutnya, yaitu 3. Berdasarkan tabel, ternyata 3 juga bilangan prima. Maka kita harus mencoret semua angka kelipatan 3.

Kita lanjut ke angka 4. Berhubung angka 4 sudah dicoret, artinya 4 bukan bilangan prima. Maka kita bisa langsung lanjut ke angka berikutnya.

Sekarang kita di angka 5. Ternyata 5 adalah bilangan prima. Maka kita coret lagi semua angka kelipatan 5.

Kita lanjutkan proses hingga ke angka 50, maka kita mendapatkan tabel yang berisi bilangan prima.

Algoritma ini bisa kita tulis dengan menggunakan struktur data Array. Jadi tabel ilustrasi pada slide sebelumnya, kita simpan datanya dalam bentuk array yang menggunakan index berupa integer. Nomor index menunjukkan angka yang hendak diperiksa apakah prima atau bukan prima. Sedangkan nilai yang disimpan oleh index tersebut menggunakan tipe data boolean. Nilai true berarti index adalah bilangan prima, sedangkan nilai false berarti index bukan bilangan prima.

Nilai akhir dari array bisa dilihat pada gambar di sebelah kanan. Berhubung ada keterbatasan ruang pada slide, maka contoh nilai array dibatasi hanya sampai angka 10.

Soal latihan pada video ini masih mirip dengan sebelumnya. Tuliskan kode untuk mencari bilangan prima yang lebih kecil dari 50. Namun kali ini harus menggunakan algoritma Sieve of Eratosthenes.

Pause terlebih dahulu video ini dan coba kerjakan latihan pada komputer masing-masing. Nantinya kita akan kembali untuk membahas solusi dari latihan ini.

Kita akan mengerjakan latihan. Source code di layar saya ambil dari source code sebelumnya, sebagai dasar untuk mengerjakan latihan. Disini ada function getPrimes, yang bertujuan untuk mencari bilangan prima yang lebih kecil sama dengan nilai parameter $n. Tugas kita adalah mengisi function ini. Sedangkan di luar function ada beberapa fungsi untuk mengukur waktu, yang sudah pernah kita bahas pada video sebelumnya. Untuk sementara kita panggil function getPrimes dengan argument 10 dahulu ya. Nantinya kalau kode sudah berjalan benar, nilai ini bisa kita ganti menjadi berapa saja.

Pertama kita buat dahulu variable $isPrimes yang berisikan array yang nilai awalnya true semua. Caranya? Kita panggil saja function array_fill. Berhubung biasanya di pemograman nomor index array dimulai dari 0, jadi argument pertama kita isi dengan nilai 0 ya. Argument keduanya harus diisi dengan $n + 1, karena index-nya dimulai dari 0. Sedangkan argument ketiga adalah nilai dari array yaitu true.

Setelah itu kita coba var_dump isi dari $isPrimes. Kita coba jalankan. Sekarang kita memiliki array dengan index 0 hingga 10, yang berisi nilai true.

Selanjutnya. Bilangan prima memiliki aturan pengecualian, yaitu angka 0 dan 1 tidak termasuk bilangan prima. Jadi aturan pengecualian ini mesti kita masukkan ke kode terlebih dahulu. Kita ubah nilai dari index 0 menjadi false. Lalu kita ubah juga index 1 menjadi false. Kita coba jalankan. Sekarang index 0 dan 1 bernilai false, sedangkan index lainnya bernilai true.

Kita mulai periksa bilangan prima mulai dari 2 hingga n. Jadi kita buat looping for dengan nilai awal $i = 2. Kondisi $i <= $n. Perhatikan disini tanda yang digunakan adalah kecil sama dengan ya. Kemudian increment $i++.

Kita periksa kalau nilai yang disimpan oleh index $i adalah true, artinya $i adalah bilangan prima. if($isPrimes[$i]). Nah kalau kode kita berjalan masuk ke dalam if, artinya $i adalah bilangan prima. Langkah pertama yang kita lakukan adalah kita cetak nilai dari $i ditambah tanda spasi.

Langkah keduanya adalah kita ubah semua kelipatan $i menjadi false. Kita buat loop lagi dengan nilai awal $j = $i * $i. Nah, sebenarnya nilai awal dari kelipatan $i adalah $i * 2. Namun untuk keperluan optimasi, kita bisa menggunakan nilai awal $i * $i, karena nilai yang lebih kecil sudah diubah menjadi false pada iterasi sebelumnya. Kondisi loop tetap sama dengan yang pertama yaitu $j <= $n. Dan untuk incrementnya adalah nilai $j ditambah dengan nilai $i. Isi dari loop, kita ubah nilai $isPrimes[$j] menjadi false.

Di luar dari loop, kita cetak nilai PHP_EOL. Kita simpan dan coba jalankan. Kita mendapatkan hasil bilangan prima yang lebih kecil sama dengan 10. Kita cek nilai dari array sama persis dengan nilai pada slide ya.

Kalau kita hendak menyelesaikan latihan, kita tinggal hapus var_dump($isPrimes). Lalu kita ubah nilai argument getPrimes menjadi 50. Kita coba jalankan. Dan ini adalah hasil yang diharapkan.

Namun kalau kita ingin tes lebih lanjut, kita bisa ubah argument menjadi 100.000 atau bahkan 1.000.000. Jadi kita bisa bandingkan bagaimana kecepatan dari algoritma ini dengan latihan yang kita kerjakan pada video sebelumnya.

Apakah benar algoritma Sieve of Eratosthenes adalah algoritma tercepat untuk mencari bilangan prima? Teman-teman bisa bandingkan sendiri ya.

Dengan menggunakan fasilitas tanya jawab, maka Anda bisa bertanya dan akan dijawab langsung oleh instruktur kursus.

Anda belum terdaftar pada kursus ini sehingga tidak bisa mengajukan pertanyaan.