Algoritma Bilangan Prima

Bilangan prima termasuk bilangan yang cukup unik, kita sudah mempelajari bilangan ini sejak masuk sekolah dasar.

Beberapa referensi yang penulis dapat menyatakan bahwa bilangan prima merupakan bilangan positif yang hanya bisa dibagi oleh tepat 2 pembagi, yaitu angka 1 dan angka tersebut sendiri. Ada juga yang menyatakan sebagai suatu bilangan yang hanya bisa dibagi oleh dirinya sendiri tanpa menyertakan angka 1.
Contoh: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 dan seterusnya.

Dalam logika pemrograman, kita cuma perlu memperhatikan mulai angka 2 dan seterusnya. Angka 0 jelas tidak mungkin, karena bilangan ini dibagi angka berapapun akan menghasilkan angka 0. Dan angka 1 juga kita abaikan saja, sebab angka 1 hanya bisa dibagi oleh dirinya sendiri, padahal bilangan prima itu syarat utamanya bisa dibagi oleh 2 bilangan natural yang nyata, yaitu angka 1 dan dirinya sendiri. (Note: bisa dibagi ini dalam artian menghasilkan bilangan bulat positif, bukan bilangan pecahan.)

Berikutnya akan penulis ilustrasikan contoh pembagiannya, dimana kita sepakati bahwa angka pembagi tidak melibatkan angka 1.
2: hanya bisa dibagi 2.
3: hanya bisa dibagi 3.
4: bisa dibagi 2 dan 4 (lebih dari 1 pembagian, maka tidak termasuk bilangan prima).
5: hanya bisa dibagi 5.
6: bisa dibagi 2,3, dan 6 (bukan bilangan prima).
Dan seterusnya.
Misalkan diketahui sebuah bilangan X, bagaimana cara menentukan bahwa bilangan X itu termasuk bilangan prima atau bukan?
Asumsi: X adalah bilangan yang lebih besar dari 2
Berarti bilangan-bilangan yang akan menjadi pembagi adalah mulai angka 2 sampai X-1.
Jika bilangan X bisa dibagi oleh minimal salah satu dari bilangan-bilangan mulai 2 sampai X-1, maka dapat dikatakan bahwa bilangan X adalah bukan bilangan prima.
Contoh: 9
Bilangan sebagai pembagi adalah 2 3 4 5 6 7 8
Untuk mengetahui bahwa suatu bilangan bisa dibagi atau tidak, paling mudah kita menggunakan bantuan mod, yang menyatakan sisa hasil bagi. Jika sisa hasil bagi 0 berarti bisa dibagi.
Kembali ke contoh.
9 mod 2 = 1 (hasil bukan 0, artinya tidak habis/bisa dibagi), lanjutkan,
9 mod 3 =0 (sudah cukup untuk menyimpulkan bahwa 9 adalah bukan bilangan prima.)
Tidak perlu kita uji dengan membagi 9 dengan angka 4 dan seterusnya.
Contoh lain: 11
11 mod 2 = 1
11 mod 3 = 2
11 mod 4 = 3
11 mod 5 = 1
11 mod 6 = 5
11 mod 7 = 4
11 mod 8 = 3
11 mod 9 = 2
11 mod 10 = 1
Tidak ada yang menghasilkan angka 0, berarti 11 termasuk bilangan prima.
Sekarang kita coba dengan algoritma pemrogramannya.

KAMUS
  i     : integer
  bil   : integer
  prima : boolean
ALGORITMA
  prima ← false
  input (bil)
  if (bil=2) then
     prima ← true
  else
     for i ← 2 to bil-1 do
        if (bil mod i = 0) then
           prima ← false
           exit for // keluar dari looping
        else
           prima ← true
        endif
     endfor
  endif

  if (prima) then // prima=true
     output ("Bilangan Prima")
  else
     output ("Bukan Bilangan Prima")
  endif

Berikut ini Sourcode dalam bahasa c++

#include <iostream>
using namespace std;
int main()
{
int i, j, min, max, jum=0, total=0;
float rata;
bool prima;
cout << "Masukkan nilai batas bawah: ";
cin >> min;
cout << "Masukkan nilai batas atas: ";
cin >> max;
while (min > max)
{
cout << "\n\nBatas atas harus lebih besar dari batas bawah.\nMasukkan nilai batas atas: ";
cin >> max;
}
cout << endl;
for (i=min;i<=max;i++)
{
prima=false;
if (i==2)
prima=true;
else
{
for (j=2;j<i;j++)
{
if (i % j==0)
{
prima=false;
break; // keluar dari looping
}
else
prima=true;
}
}
if (prima) // prima = true
{
cout << i << "\t";
jum+=1; // menghitung banyaknya bilangan prima
total+=i; // total jumlah dari seluruh bil. prima
}
}
cout << endl;
cout.setf(ios::fixed);
cout.setf(ios::showpoint);
cout.precision(2);
rata=(float)total/jum;
cout << "\nTerdapat " << jum << " bilangan dengan total " << total;
cout << "\nRata-ratanya " << rata << endl;
return 0;
}

Demikian penjelasan tentang Algoritma bilangan prima trimakasih.