Saringan Eratosthenes adalah suatu cara untuk menemukan semua bilangan prima di antara 1 dan suatu angka n. Saringan ini ditemukan oleh Eratosthenes, seorang ilmuwan Yunani kuno. Cara ini merupakan cara paling sederhana dan paling cepat untuk menemukan bilangan prima, sebelum Saringan Atkin
ditemukan pada tahun 2004. Saringan Atkin merupakan cara yang lebih
cepat namun lebih rumit dibandingkan dengan Saringan Eratosthenes.
Langkah-Langkah Saringan Erathostenes
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.
 |
| Animasi saringan Eratosthenes dari 1 sampai n=120. Daftar A (kiri) dan daftar B (kanan). Bilangan yang sudah diwarnai artinya sudah dicoret. |
Saringan Eratosthenes adalah suatu cara untuk menemukan semua bilangan prima di antara 1 dan suatu angka n. Saringan ini ditemukan oleh Eratosthenes, seorang ilmuwan Yunani kuno. Cara ini merupakan cara paling sederhana dan paling cepat untuk menemukan bilangan prima, sebelum Saringan Atkin
ditemukan pada tahun 2004. Saringan Atkin merupakan cara yang lebih
cepat namun lebih rumit dibandingkan dengan Saringan Eratosthenes. 
0 Response to "Saringan Eratosthenes"
Post a Comment
BERI KOMENTAR | SIAPAPUN BISA BERKOMENTAR
Ayo berpartisipasi membangun budaya berkomentar yang baik.
Kolom komentar tersedia untuk diskusi, berbagi ide dan pengetahuan.
Hargai pembaca lain dengan berbahasa yang baik dalam berekspresi. Setialah pada topik.
Jangan menyerang atau menebar kebencian terhadap suku, agama, ras, atau golongan tertentu.
Kata-kata yang tak pantas akan segera disensor oleh sistem.
Segala bentuk link yang bersifat promosi semata tanpa ada komentar kepada pembaca, maka saya berhak menghapus komentar tersebut tanpa basa-basi.
ORANG YANG BERKOMENTAR
Annonymus : Bagi agan-agan yang tidak mempunyai akun Google
Google : Apabila agan-agan memiliki akun Google
Name/URL : Bagi agan-agan yang dapat mencantumkan nama dan link sobat
TAG KOMENTAR
Agan-agan juga bisa menggunakan tag <b>...</b> untuk menebalkan tulisan, tag <i>...</i> untuk memiringkan tulisan, dan tag <u>...</u> untuk memberikan garis bawah.
Siapapun dapat mengomentari artikel ini, tanpa harus menggunakan chapca.
Thanks udah mau berkunjung ke blog saya agan-agan yang baik...