Algoritma Simpel untuk Mencari Bilangan Prima (Bash Script)

Untuk mencari bilangan prima sendiri sangatlah mudah, dan merupakan salah satu hal yang paling dasar dalam programming.

Berbagai algoritma sudah di kembangkan, yang tentunya dapat meningkatkan efisiensi waktu program.

Namun, untuk tutorial kali ini, saya akan menggunakan cara paling basic (paling manusiawi) hehehe

Bilangan prima adalah bilangan yang hanya dapat di bagi dengan dirinya dan 1.
Apakah 2 termasuk prima ? Ya, karena 2 hanya dapat dibagi 2 dan 1
Apakah 3 termasuk prima ? Ya, karena 3 hanya dapat dibagi 3 dan 1
Apakah 1 termasuk prima ? Tidak, karena 1 hanya dapat di bagi 1 (Alasan lanjut dapat ditemukan di sini)
Apakah 4 termasuk prima ? Tidak, karena 4 dapat di bagi 1, 2, dan 4

Jadi pada dasarnya, bilangan prima hanya dapat di bagi dengan 2 bilangan.

Jika kita ingin program kita menampilkan seluruh bilangan prima dari 1 hingga N, kita perlu:
- Buat program yang melakukan looping i dimana i merupakan 1 -> N
- Untuk setiap iterasi i, lakukan looping pembagian i dibagi 1 -> i
- Setiap kali pembagian berhasil di lakukan, naikkan counter k (k=k+1)
- Pada akhir looping pembagian, cek nilai k. Jika k bukan 2, maka bilangan tersebut bukan prima. Jika k = 2, maka bilangan tersebut adalah prima, tampilkan pada layar.
- Reset k = 0.
- Lakukan iterasi selanjutnya, hingga batas yang di tentukan


Berikut bash script nya :

#---------------------------------------------------------------------------------------------------------
#!/bin/bash
x=$1
i=1

while [ $i -le $x ];
do
k=0
for a in `seq 1 $i` ;
do
if [ $(( i%a )) -eq 0 ];
then
let "k=$k+1"
fi
done
if [ $((k)) -eq 2 ];
then
echo $i
fi
let "i=$i+1"
done
#---------------------------------------------------------------------------------------------------------

Berikut ketika program di jalankan:

And that's it guys. Algoritma di atas berlaku untuk semua bahasa pemrograman, bukan hanya bash. Masih banyak algoritma lain untuk mencari bilangan prima, misalnya algoritma Sieve of Eratosthenes yang lebih efisien dari segi waktu eksekusi.

Related Post: