Cara Cepat Menghitung Bilangan Prima

316 views

Cara cepat menghitung bilangan prima

Ahli Matematika Harald Helfgott menjadi terkenal pada tahun 2013. Dia baru saja menyelesaikan masalah 271 tahun yang dikenal sebagai dugaan lemah Goldbach. Menurut teori ini, setiap bilangan ganjil yang lebih besar dari 5 juga dapat ditulis sebagai penjumlahan 3 bilangan prima. Misalnya, 3 + 3 + 5 = 11 dan 19 + 13 + 3 = 35

Helfgott, 38 tahun, bahkan melangkah lebih jauh ke masa lalu untuk memecahkan masalah. Dia datang dengan versi perbaikan dari saringan Eratosthenes, metode populer untuk menemukan bilangan prima yang ditemukan sekitar 240 SM. Versi baru Helfgott akan mengurangi seberapa banyak ruang fisik yang diperlukan dalam memori komputer. Ini akan mengurangi jumlah program waktu yang diperlukan untuk membuat perhitungan itu.

Cara Cepat Menghitung Bilangan Prima
Saringan gigi mekanis yang dibuat oleh Profesor Matematika dari University of California, Derrick N Lehmer, Berkeley, California, 1932. Ini digunakan untuk memecahkan masalah teori angka dan dapat memeriksa 5.000 kombinasi per detik, sebuah rekor yang hanya dikalahkan kemudian oleh komputer di 1960an

Bilangan prima adalah sesuatu seperti “atom matematika.” Mereka adalah angka yang hanya dapat dibagi oleh bilangan itu sendiri dan angka 1. Eratosthenes dari Cyrene seorang matematikawan, astronom dan geografi Yunani – menemukan metode praktis untuk mengidentifikasi mereka: “saringan,” atau filter. “Seperti banyak anak lain, saya diajarkan ini di sekolah dasar ketika saya berusia 10 tahun, dengan meja,” kata Helfgott, yang saat ini menjadi peneliti di Pusat Penelitian Ilmiah Nasional dan Universitas Göttingen

Mencoret Angka
Untuk menggunakan saringan ini untuk menemukan semua bilangan prima antara 1 dan 100, misalnya, pertama harus menuliskan daftar angka dalam urutan numerik. Kemudian seseorang mulai mencoretnya dalam urutan tertentu. Pertama, satu menghilangkan semua kelipatan 2 (kecuali 2). Kelipatan adalah semua angka yang dapat dibagi secara merata oleh angka tertentu. Kelipatan 2 adalah 4, 6, 8, 10, dll. Setelah ini dilakukan, satu mencoret semua kelipatan 3 (kecuali 3), kelipatan 4 (kecuali 4), dan seterusnya, dimulai dengan nomor berikutnya yang belum dicoret. Angka-angka yang tersisa di akhir akan menjadi bilangan prima. Metode ini dapat ditulis sebagai algoritma, atau proses langkah demi langkah. Komputer dapat menjalankannya dengan sangat cepat.

Ketika mengerjakan sebuah buku tentang dugaan lemah Goldbach, Helfgott mulai memikirkan masalah saringan Eratosthenes. Secara khusus, dia berpikir tentang berapa banyak ruang atau memori yang dibutuhkannya. “Komputer saat ini sangat cepat,” kata Helfgott. “Tapi ingatannya masih terbatas.”

Menilai Algoritma
Matematikawan Jean Carlos Cortissoz Iriarte mengatakan ada dua hal yang harus dilihat untuk melihat seberapa bagus suatu algoritma. Pertama, kita harus melihat jumlah langkah per bit yang diberikan input. Kemudian kita harus melihat berapa banyak bit yang perlu disimpan dalam memori sementara langkah-langkah dari algoritma dijalankan. Dalam hal jumlah langkah per bit, saringan Eratosthenes “relatif efisien,” kata Cortissoz Iriarte. Tetapi ketika algoritma digunakan untuk mencari bilangan prima untuk bilangan yang sangat besar, ini membutuhkan banyak memori. Pada saat itu, saringan “berhenti menjadi efisien.”

Helfgott menemukan cara untuk menyesuaikan saringan Eratosthenes untuk menggunakan lebih sedikit ruang memori. Untuk menemukan semua bilangan prima hingga satu triliun, versi baru Helfgott jauh lebih efisien. Hanya “membutuhkan beberapa juta bit, bukan satu miliar bit,” kata Helfgott. Ide-idenya dipresentasikan pada bulan Juli pada konferensi di Buenos Aires, Argentina, dan Paris, Prancis.

Saringan Eratosthenes Adalah Spesial
Untuk memahami keuntungan dari saringan baru, Cortissoz Iriarte menawarkan perbandingan. “Mari kita berpura-pura bahwa Anda adalah komputer,” katanya. Untuk menyimpan informasi dalam ingatan Anda, “Anda menggunakan lembaran kertas. Jika menghitung bilangan prima antara 1 dan 1.000.000, Anda perlu 200 rim kertas (10.000 lembar) … dengan algoritma yang diusulkan oleh Helfgott Anda hanya akan membutuhkan seperlima dari rim (sekitar 100 lembar), ”katanya.

Ada saringan atau algoritme lain untuk mengidentifikasi bilangan prima. Namun Helfgott mencatat bahwa saringan Eratosthenes adalah istimewa. Ia juga dapat bekerja dengan operasi matematika lain seperti faktorisasi. Metode ini memecah nomor apa pun ke dalam produk bilangan prima dan digunakan untuk menyandikan informasi dengan cara yang aman, seperti untuk melakukan transfer bank elektronik atau pembelian online. “Faktorisasi menjadi elemen kunci” dari peradaban modern, kata Helfgott. Eratosthenes tidak akan pernah membayangkannya.

Cara Cepat Menghitung Bilangan Prima

Tinggalkan Balasan

Alamat email Anda tidak akan dipublikasikan. Ruas yang wajib ditandai *

Situs ini menggunakan Akismet untuk mengurangi spam. Pelajari bagaimana data komentar Anda diproses.