Setelah mencari di Google, ternyata saya menemukan salah satu algoritma klasik untuk mencetak bilangan prima. Algoritma tersebut disebut sebagai Sieve of Eratosthenes, saya temukan di Wikipedia. mungkin ini bukan algoritma yang tercepat, tapi setidaknya sudah cukup cepat dibanding jika menggunakan modulus.
Berikut ini algoritma tersebut yang dikutip dari Wikipedia.
Misalkan kita hendak menemukan semua bilangan prima di antara 1 sampai suatu bilangan bulat n.
- Tulis semua bilangan, mulai dari 1 sampai n. Misalkan ini adalah daftar A.
- Buat suatu daftar yang masih kosong, sebut saja daftar B.
- Coret bilangan 1 dari daftar A.
- Lalu tulis 2 pada daftar B. Lalu coret 2 dan semua kelipatannya dari daftar A
- Bilangan pertama yang belum tercoret dari daftar A (misalnya 3) adalah bilangan prima. Tulis bilangan ini di daftar B, lalu coret bilangan ini dan semua kelipatannya dari daftar A.
- Ulangi langkah 4 sampai semua bilangan di daftar A sudah tercoret.
Setelah selesai, semua bilangan di daftar B adalah bilangan prima.
Tidak ada komentar:
Posting Komentar