Tentang saringan Eratosthenes - saringan prima tertua
Saringan Eratosthenes menemukan semua bilangan prima sampai suatu batas tanpa satu pun pembagian. Anda cukup menghitung: coret setiap bilangan kedua setelah 2, setiap bilangan ketiga setelah 3, dan seterusnya. Yang tersisa adalah bilangan prima. Lebih dari dua ribu tahun kemudian, ini masih salah satu cara tercepat untuk mendaftarnya.
Eratosthenes dari Kirene
Eratosthenes hidup sekitar tahun 276 sampai 194 SM dan memimpin Perpustakaan Agung Aleksandria. Ia paling dikenal karena mengukur ukuran Bumi dari panjang bayangan di dua kota. Saringan ini dinamai menurut namanya karena Nikomakhos dari Gerasa menggambarkannya sebagai metodenya dalam Pengantar Aritmetika, yang ditulis sekitar tahun 100 M.
Cara kerja saringan
Tulis bilangan dari 2 sampai N. Bilangan pertama, 2, adalah prima: coret 4, 6, 8, dan setiap kelipatan 2 lainnya. Bilangan berikutnya yang tersisa, 3, adalah prima: coret 9, 12, 15, dan seterusnya. Lanjutkan dengan 5, 7, dan bilangan berikutnya yang tersisa. Bilangan yang tidak pernah dicoret tidak punya faktor yang lebih kecil, jadi bilangan itu prima.
Berhenti di akar kuadrat
Setiap bilangan komposit sampai N punya faktor prima yang tidak lebih besar dari akar kuadrat N. Jadi begitu p² lebih besar dari N, tidak ada lagi yang perlu dicoret. Untuk bilangan prima sampai 100 Anda hanya perlu 2, 3, 5, dan 7, dan untuk 1000 bilangan prima sampai 31.
Seberapa cepat?
Saringan ini butuh sekitar N log log N langkah, yang tumbuh hanya sedikit lebih cepat daripada N itu sendiri. Komputer masih memakainya, sering kali per bagian sebagai saringan tersegmentasi, untuk mendaftar bilangan prima sampai miliaran. Untuk menguji apakah satu bilangan besar adalah prima, metode lain lebih cepat.
Pertanyaan yang sering diajukan
Siapa yang menemukan saringan Eratosthenes?
Saringan ini dinamai menurut Eratosthenes dari Kirene, seorang cendekiawan Yunani abad ketiga SM. Deskripsi tertulis tertua berasal dari Nikomakhos dari Gerasa, sekitar tahun 100 M.
Mengapa saringan mulai mencoret dari p²?
Setiap kelipatan p yang lebih kecil punya faktor prima yang lebih kecil, jadi bilangan prima yang lebih kecil sudah mencoretnya.
Ada berapa bilangan prima di bawah 1000?
Ada 168 bilangan prima di bawah 1000. Yang terbesar adalah 997.
Related alat
Saringan Eratosthenes
Lihat saringan Eratosthenes menemukan bilangan prima sampai 100, 200, 500, atau 1000. Setiap bilangan prima mencoret kelipatannya dengan warnanya sendiri, langkah demi langkah.
Spiral Ulam
Gambar spiral Ulam di peramban Anda. Tandai bilangan prima, baca polinomial kuadrat pada setiap diagonal, dan buka deret 40 bilangan prima Euler yang tak terputus.
Spiral Ulam
Bagaimana spiral Stanisław Ulam tahun 1963 menata bilangan bulat pada kisi persegi, mengapa bilangan prima berkumpul pada diagonal kuadrat, dan di mana empat puluh bilangan prima Euler berada saat spiral dimulai dari 41.
Konjektur Collatz
Jelajahi masalah Collatz 3n+1 di browser Anda. Telusuri barisan hujan es, tumbuhkan pohon Collatz geometris, dan perbesar fraktal Collatz kontinu.
Siap ke coba itu?
Buka PictorX di browser Anda — tidak instalasi, tidak credit kartu diperlukan ke mulai.
Coba saringan Eratosthenes