#BelajarPython 1: Bermain dengan Bilangan Prima

Setelah sekian lama, ternyata rindu juga mengkode sebuah program. Termasuk rindu bermain-main dengan bilangan.

Kali ini saya sedang tertarik untuk mempelajari bahasa Python. Bahasa pemrograman serba guna dan powerful yang bisa digunakan untuk berbagai keperluan, semisal untuk analisis data, visualisasi data, machine learning, hingga natural language processing (NLP).

Namun, pada kesempatan ini saya tak akan membahas topik-topik tersebut. Saya akan mengawali dengan menulis kode sederhana yaitu kode untuk menentukan sebuah bilangan termasuk ke dalam bilangan prima atau bukan.

Sebelum beranjak, mari ingat kembali apa itu bilangan prima? Bilangan prima adalah bilangan bulat positif yang hanya bisa dibagi dengan dirinya sendiri, akan menghasilkan sisa jika dibagi dengan bilangan bulat positif lainnya. Contoh bilangan prima antara 0 – 10 adalah 1, 3, 5, dan 7.

Lalu bagaimana cara menentukan sebuah bilangan termasuk bilangan prima atau bukan. Kita bisa menyiasatinya dengan konsep operasi modulus.

Operasi modulus adalah sebuah operasi yang menghasilkan sisa pembagian dari suatu bilangan terhadap bilangan lainnya. Dalam bahasa pemrograman, operasi ini umumnya dilambangkan dengan simbol %, mod atau modulo.

Jadi secara singkat, algoritma untuk menentukan sebuah bilangan prima yaitu:

1. Masukkan bilangan yang akan diuji, misal diwakili dengan variabel angka
2. Cek angka, apakah termasuk bilangan bulat positif atau bukan
3. Cek angka, apakah habis dibagi dengan faktor pembagi secara berurutan mulai dari 2 (batas bawah) hingga bilangan itu sendiri
4. Jika ditemukan faktor pembagi, maka angka BUKAN bilangan prima dan program berhenti (iterasi tidak dilanjutkan, biasanya diakali dengan fungsi break)
5. Jika tak ditemukan faktor pembagi atau sisa modulus tidak sama dengan 0, maka bilangan tersebut adalah bilangan prima

Kode program

# meminta input dari user

angka = int(input("Masukkan angka: "))

# mengecek bilangan prima selalu lebih besar dari 1

if angka > 1:

   # mengecek faktor pembagi dengan operasi modulus

   for i in range(2,angka):
       if (angka % i) == 0:
           print angka,"bukan bilangan prima"
           print "karena", i,"dikalikan",angka//i,"hasilnya adalah",angka
           break
   else:
       print angka,"adalah bilangan prima"

# keluaran jika sebuah bilangan kurang dari atau sama dengan 1

else:
   print angka,"is not a prime number"

Output

Membangkitkan bilangan prima

Setelah melihat kode di atas barangkali ada yang punya ide, bagaimana jika bilangan prima itu dibangkitkan dari sebuah aturan. Misal dengan pertanyaan bilangan mana saja yang termasuk bilangan prima di antara 30 hingga 100?

Kode program menjadi semakin menantang dan menarik. Secara singkat, algoritma untuk menjawab pertanyaan itu adalah sebagai berikut:

1. Tentukan batas bawah dan batas atas bilangan yang akan dicari, misal dengan variabel angka1 (batas bawah) dan angka2 (batas atas)
2. Pastikan angka1 dan angka2 adalah bilangan bulat positif
3. Cek dengan iterasi operasi modulus, dimulai dari angka1 hingga angka2
4. Tampilkan bilangan prima yang memenuhi syarat modulus tidak sama dengan 0

Kode program

# Meminta input angka batas bawah dan batas atas

angka1 = input("Masukkan batas bawah: ")
angka2 = input("Masukkan batas atas: ")

# membangkitkan bilangan prima

if angka1 >= 1 and angka2 > 1:
    for x in range(angka1,angka2):
        prima = True
        for i in range(2,x):
            if (x%i==0):
                prima = False
        if prima == True:
           print x

else:
    print "Harus bilangan bulat positif. Tidak boleh negatif dan desimal."

Output

Kelemahan kode program di atas adalah kode program tersebut hanya bisa menangani hingga batas digit tertentu. Untuk itu perlu sebuah algoritma yang lebih kompleks, efisien, dan juga cepat. Lebih dari itu, mesin komputasi yang digunakan juga harus lebih andal untuk menghitung miliaran lebih iterasi.

Jika ingin membaca beberapa algoritma yang paling cepat untuk jumlah bilangan yang sama, bisa baca-baca analisis seputar bilangan prima ini di sini atau di sini.

Bilangan prima terbesar

Euclides, pakar matematika di abad ke-4 pernah membuktikan bahwa di dunia ini tak ada bilangan prima terbesar. Artinya, dari bilangan prima terbesar yang diketahui hingga saat ini, pastilah ada bilangan prima setelahnya yang lebih besar.

Teka teki bilangan prima ini dimanfaatkan para matematikawan untuk menemukan bilangan prima yang lebih besar dari bilangan yang ditemukan hingga saat ini. Selain menggunakan persamaan matematis untuk membuktikan bilangan prima, penentuan itu juga dibantu dengan mesin komputasi (komputer).

Bilangan prima terbesar saat ini ditemukan tahun 2013, yang mempunyai 17.425.170 digit, direferensikan dengan nomer M_57885161 , yang berarti bilangan tersebut adalah hasil dari 2_57885161 – 1. Bilangan itu ditemukan dari proyek distribusi komputasi Great Internet Mersenne Prime Search (GIMPS).

Berikut ini adalah grafik penemuan bilangan prima terbesar dari tahun ke tahun, berdasarkan tahun penemuan dan jumlah digit.

Apa bilangan prima selanjutnya dan kapan ditemukan lagi? Hanya waktu yang bisa menjawab.

Bahan bacaan:

• https://en.wikipedia.org/wiki/Prime_number
• https://id.wikipedia.org/wiki/Bilangan_prima_terbesar_yang_diketahui