Description

Narasi (Story Telling)

Di sebuah dunia digital, matematika dan pemrograman bersatu untuk memecahkan tantangan klasik: menemukan bilangan prima. Dua pendekatan muncul Brute Force, yang lambat namun sederhana, dan Sieve of Eratosthenes, yang cepat dan cerdas. Seorang pemrogram pun memutuskan untuk menguji keduanya menggunakan Python. Dengan logika sederhana, Brute Force mencoba memeriksa satu per satu, sementara Sieve of Eratosthenes menyaring angka dengan efisiensi luar biasa. Hasilnya? Sieve membuktikan dirinya jauh lebih unggul. Dengan program ini, sang pemrogram belajar bahwa algoritma yang tepat dapat mengubah tantangan besar menjadi solusi cerdas.

Latar Belakang

Bilangan prima merupakan salah satu konsep dasar dalam matematika yang memiliki peran penting dalam berbagai bidang, termasuk kriptografi dan teori bilangan. Sebagai angka yang hanya bisa dibagi oleh 1 dan dirinya sendiri, bilangan prima menjadi fondasi dalam sistem keamanan data yang digunakan oleh banyak teknologi modern. Namun, meskipun konsep bilangan prima sederhana, menemukan semua bilangan prima dalam rentang yang besar bisa menjadi tantangan besar, terutama dengan metode yang tidak efisien. Dalam dunia pemrograman, penting untuk mencari solusi yang tidak hanya benar, tetapi juga cepat dan efisien. Dalam konteks ini, pemrograman Python menjadi alat yang sangat berguna untuk mengimplementasikan berbagai algoritma dalam mencari bilangan prima. Dua pendekatan populer yang sering digunakan adalah Brute Force dan Sieve of Eratosthenes. Brute Force adalah cara yang lebih sederhana tetapi memakan waktu, sedangkan Sieve of Eratosthenes merupakan metode yang lebih canggih dan lebih cepat, terutama untuk angka-angka besar. Dengan menguji kedua metode ini, program ini bertujuan untuk menunjukkan bagaimana pemrograman dan algoritma yang tepat dapat mengubah cara kita menyelesaikan masalah matematika yang tampaknya sederhana, tetapi penuh tantangan.

Pengertian Kode

Kode yang dibuat bertujuan untuk mencari dan membandingkan bilangan prima hingga suatu batas yang diberikan oleh pengguna. Dua pendekatan yang digunakan untuk menghitung bilangan prima adalah Brute Force dan Sieve of Eratosthenes. Berikut adalah penjelasan tentang fungsi dan alur kerja dari kode yang dibuat:

is_prime_brute_force(n):

• Fungsi ini mengecek apakah suatu angka n adalah bilangan prima dengan cara membaginya dengan semua angka dari 2 hingga /n​ (akar kuadrat dari n).
• Jika ada angka pembagi selain 1 dan n sendiri, maka angka tersebut bukan bilangan prima.
• Logika: Jika angka n tidak dapat dibagi oleh angka lain kecuali 1 dan dirinya sendiri, maka angka tersebut adalah bilangan prima.

primes_brute_force(limit):

• Fungsi ini menggunakan metode Brute Force untuk mencari semua bilangan prima hingga batas yang ditentukan (parameter limit).
• Fungsi ini memanggil is_prime_brute_force untuk setiap angka dari 2 hingga limit untuk memeriksa apakah angka tersebut prima atau tidak.
• Hasilnya adalah daftar bilangan prima yang ditemukan.

sieve_of_eratosthenes(limit):

• Fungsi ini mengimplementasikan algoritma Sieve of Eratosthenes, yang lebih efisien untuk mencari bilangan prima.
• Langkah-langkahnya:
  • Buat daftar angka dari 2 hingga limit, dan tandai semuanya sebagai prima.
  • Mulai dengan angka 2, dan tandai semua kelipatan angka tersebut (misalnya, 4, 6, 8, ...) sebagai bukan bilangan prima.
  • Lanjutkan ke angka berikutnya yang belum ditandai dan ulangi proses ini hingga akar kuadrat dari limit.
• Keunggulan: Dengan algoritma ini, hanya bilangan prima yang tetap berada di dalam daftar, sementara yang lainnya dihapus.

benchmark(limit):

• Fungsi ini digunakan untuk menguji kinerja kedua metode.
• Fungsi ini pertama-tama menghitung bilangan prima menggunakan metode Brute Force dan mengukur waktu yang diperlukan.
• Kemudian, fungsi ini menghitung bilangan prima menggunakan metode Sieve of Eratosthenes dan mengukur waktu yang diperlukan.
• Hasil waktu dari kedua metode dibandingkan untuk menunjukkan mana yang lebih efisien.

if __name__ == "__main__"::

• Bagian utama dari program yang meminta input dari pengguna untuk menentukan batas angka (misalnya 100 atau 1000).
• Setelah itu, fungsi benchmark dipanggil untuk membandingkan kedua metode dalam menghitung bilangan prima hingga batas yang diberikan.

Penjelasan Program

1. Fungsi is_prime_brute_force:
   • Mengecek apakah sebuah angka prima menggunakan pembagian hingga akar kuadrat dari angka.
2. Fungsi primes_brute_force:
   • Menggunakan metode brute force untuk mencari semua bilangan prima hingga batas tertentu.
3. Fungsi sieve_of_eratosthenes:
   • Mengimplementasikan algoritma Sieve of Eratosthenes untuk menemukan semua bilangan prima hingga batas tertentu.
4. Fungsi benchmark:
   • Membandingkan kecepatan kedua metode untuk melihat efisiensinya dalam praktik.

Contoh Output

Jika dijalankan dengan input 100000:

Big-O Analysis

• Brute Force: O(n/n)
• Sieve of Eratosthenes: O(n log n log n)

Program ini efektif untuk mempelajari efisiensi algoritma menggunakan Big O.

Kesimpulan

Dalam Portofolio ini, saya telah mengimplementasikan dua metode untuk mencari bilangan prima menggunakan Python: Brute Force dan Sieve of Eratosthenes. Kedua metode tersebut menunjukkan cara yang berbeda dalam menyelesaikan masalah yang sama, dengan Sieve of Eratosthenes terbukti lebih efisien dibandingkan dengan Brute Force, terutama untuk jumlah angka yang besar. Melalui benchmark yang dilakukan, kita dapat melihat perbedaan signifikan dalam hal waktu eksekusi antara kedua metode ini.