Sejak berada di tingkat sekolah dasar, kita sudah diperkenalkan dengan beberapa jenis bilangan. Mulai dari bilangan yang dipakai untuk mencacah, yakni bilangan asli (1, 2, 3, dan seterusnya), kemudian dikerucutkan menjadi bilangan ganjil (1, 3, 5, dan seterusnya) dan bilangan genap (2, 4, 6, dan seterusnya). Di sini ceritanya kita masih belum mengenal bilangan negatif, ya.
Berikutnya, kita dikenalkan dengan sekelompok bilangan yang memiliki karakteristik yang unik, yaitu bilangan yang hanya memiliki dua faktor/pembagi. Contohnya adalah 7, yang hanya habis dibagi oleh 1 dan 7 sehingga ia memiliki dua faktor. Bilangan semacam itu disebut sebagai bilangan prima (prime number), sedangkan bilangan lain yang memiliki lebih dari dua faktor disebut sebagai bilangan komposit (composite number). Contoh bilangan prima terkecil yang kita ketahui adalah $2, 3, 5, 7, 11, 13, 17,$ dan seterusnya.
Bilangan prima banyak sekali dipakai penggunaannya dalam dunia komputer, apalagi era saat ini mengharuskan manusia berkutat dengan digitalisasi. Namun, pada dasarnya, kita belum menemukan cara yang efektif dan efisien untuk menentukan suatu bilangan termasuk prima atau tidak jika hanya menatap secara sekilas, terutama untuk kasus bilangan-bilangan yang nilainya besar. Meskipun demikian, canggihnya komputer saat ini mampu menemukan bilangan prima sampai jauh di luar bayangan kita. Bilangan prima terbesar yang diketahui saat ini adalah $2^{77.232.917}-1$ (dan mungkin akan lebih besar lagi), jelas itu adalah bilangan yang tidak terbayang betapa besar nilainya.
Baca Juga: Sistem Bilangan – Konversi dan Cara Hitungnya
Sebelum komputer menginvasi (= mempermudah) pekerjaan manusia, orang-orang pada zaman dahulu berusaha menemukan teknik atau cara yang dapat dipakai untuk menentukan bilangan prima dengan mudah tanpa harus mengecek satu per satu. Salah satunya adalah dengan menggunakan algoritma sederhana yang dikenal sebagai Saringan Eratosthenes (Sieve of Eratostehenes), atau kadang disebut sebagai Tapis Eratosthenes. Sesuai namanya, algoritma ini dibuat oleh Eratosthenes, salah satu ilmuwan legendaris kebanggaan Yunani pada abad ke-3 Sebelum Masehi. Karena telah ditemukan sejak dahulu kala, kadang-kadang algoritma ini disebut sebagai algoritma yang primitif, tetapi tidak ada salahnya bila kita mempelajari bagaimana algoritma ini bekerja.
Sekarang, kita akan mencoba menentukan bilangan prima yang terletak pada rentang bilangan $1$ sampai $100$ dengan menggunakan Saringan Eratosthenes. Saringan Eratosthenes melibatkan penggunaan bilangan prima yang “kecil” untuk menguji. Algoritma berhenti ketika kuadrat dari bilangan prima yang kita uji bernilai lebih besar dari bilangan terakhir pada rentang bilangan yang kita tentukan. Dalam kasus ini, bilangan terakhir itu adalah $100.$ Karena $11$ adalah bilangan prima dan kita tahu bahwa $11^2 = 121 > 100,$ maka algoritma seharusnya sudah berhenti sebelum ini.
Quote by Abdurrahman Wahid
1. Tuliskan bilangan 1 sampai 100
Untuk mempermudah, jangan tuliskan semua bilangan itu secara beruntun ke samping, melainkan menggunakan tabel/kisi seperti di bawah ini. Tabel/kisinya berukuran $10 \times 10,$ artinya ada $10$ baris dan $10$ kolom.
2. Tandai bilangan 1
Perhatikan bahwa 1 bukan termasuk bilangan prima karena hanya memiliki satu faktor sehingga kita tandai dengan memberi warna tertentu atau bisa juga disilang/dilingkar.
3. Tandai bilangan kelipatan 2, kecuali 2
Karena 2 adalah bilangan prima, jangan tandai. Tandai semua bilangan kelipatan 2 yang lain dengan warna tertentu, disilang, atau dilingkar.
4. Tandai bilangan kelipatan 3, kecuali 3
Prinsipnya sama. Tandai semua bilangan kelipatan 3, kecuali 3, dengan warna tertentu, disilang, atau dilingkar. Bilangan yang sudah ditandai sebelumnya tidak perlu ditandai lagi.
4. Tandai bilangan kelipatan 5, kecuali 5
Lakukan hal yang sama.
5. Tandai bilangan kelipatan 7, kecuali 7
Lakukan hal yang sama.
Algoritma berhenti sampai di sini karena bilangan prima berikutnya adalah $11$ dan kita tahu bahwa $11^2 = 121 > 100.$ Bilangan yang TIDAK kita tandai adalah bilangan prima.
Jadi, bilangan prima dari rentang bilangan 1 sampai 100 adalah 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, dan 97.
Bagaimana dengan bilangan prima yang terletak pada rentang bilangan $101$ sampai $200$? Mari kita coba selidiki dengan menggunakan Saringan Eratosthenes.
1. Tuliskan bilangan 101 sampai 200
2. Tandai bilangan kelipatan 2
3. Tandai bilangan kelipatan 3
4. Tandai bilangan kelipatan 5
5. Tandai bilangan kelipatan 7
6. Tandai bilangan kelipatan 11
7. Tandai bilangan kelipatan 13
Algoritma berhenti sampai di sini karena bilangan prima berikutnya adalah $17$ dan kita tahu bahwa $17^2 = 289 > 200.$ Bilangan yang TIDAK kita tandai adalah bilangan prima. Jadi, bilangan prima dari rentang bilangan 101 sampai 200 adalah 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, dan 199.
Bagaimana? Menarik, bukan? Algoritma ini memang cukup efektif dan efisien untuk diterapkan, meskipun kita tentu merasa bahwa kita memerlukan algoritma yang lebih powerful lagi. Dari apa yang kita kerjakan, kita mungkin sudah mendapatkan ide mengapa algoritma ini disebut sebagai “saringan”, yakni karena dari sekumpulan bilangan yang ada, kita menyaring (memilah) bilangan-bilangan yang tidak berkelipatan bilangan prima. Nah, sebagai latihan, kita bisa mencoba mencari bilangan prima dari rentang bilangan 201 sampai 1.000 dengan menerapkan algoritma yang sama.
Maksudnya kok sampai 200 kan cuman 100