Working With Primes

Prime number is natural number greater than 1 that has no positive divisors other than 1 and itself. (taken from wikipedia)

Singkatnya, bilangan prima adalah bilangan asli yang bernilai lebih dari 1, yang tidak memiliki pembagi positif selain 1 dan dirinya sendiri. Contoh, 7 hanya dapat dibagi oleh 1 dan 7 saja, oleh karena itu, 7 adalah bilangan prima. Contra-example, 27 dapat dibagi dengan 1, 3, 9, dan 27, oleh karena itu 27 bukan bilangan prima.


Berikut beberapa penggunaan bilangan prima:

Primality Test
Primality test adalah istilah untuk mengecek apakah suatu bilangan merupakan bilangan prima atau bukan. Secara garis besar, ada dua metode dalam primality test, yaitu deterministic dan probabilistic.
Deterministic memiliki arti bahwa prosedur/algoritma yang kita miliki, apabila dijalankan, pasti mengembalikan nilai yang sesuai/pasti (dapat diprediksi).
Probabilistic (atau Randomized) berkebalikan dengan deterministic. Algoritma ini bekerja dengan berdasar kepada suatu ketidakteraturan (randomness) dalam proses bekerjanya. Jadi, nilai yang kita dapat setelah algoritma dijalankan, tidak dapat dipastikan 100% kebenarannya.

Probabilistic
Probabilistic primality test yang akan dibahas:

Fermat Primality Test:
Dari Fermat's Little Theorem, dapat dilihat bahwa untuk p sebuah bilangan prima dan a  bukan kelipatan dari p, maka berlaku:



Maka, untuk menentukan apakah suatu bilangan n prima atau tidak, kita coba a untuk bilangan-bilangan dalam range [1,n). Apabila dalam sekian kali percobaan, hasil kongruensi sesuai seperti teorema Fermat di atas, maka n kemungkinan prima.

Deterministic
Metode deterministic lebih sering digunakan, karena lebih pasti hasilnya. Namun, biasanya cukup lambat untuk bilangan yang cukup besar.

Trial Division Method:
Metode ini adalah metode paling 'melelahkan', namun paling sering digunakan diawal-awal belajar mengenai primality testing.
Inti dari trial division adalah untuk suatu bilangan n, apabila n dapat dibagi dengan suatu nilai i, dengan i adalah bilangan-bilangan dalam range [2,n-1], maka n adalah bilangan komposit. Jika tidak, maka jelas bahwa n adalah prima.

Source code (pascal):

function trial_div ( x : integer ) : boolean;
var
  i : integer;
begin
  trial_div := true;
  for i := 2 to x-1 do
    if (x mod i = 0) then
    begin
      trial_div := false;
      break;
    end;
end;

Sebenarnya, implementasi dari trial division berdasarkan pengertian di atas masih terlalu boros/inefisien. Ada beberapa pengamatan tambahan yang dapat menambah efisiensi algoritma ini:

• Pengecekan tidak perlu dilakukan dalam range [ 2, n-1 ], cukup dari [ 2, n^(0.5) ]. Mengapa? Faktor-faktor n yang bernilai dalam range [ n^(0.5), n ] merupakan hasil dari n dibagi dengan faktor-faktor n yang bernilai dalam range [ 1, n^(0.5) ]. Sehingga, merupakan pemborosan jika mencoba-coba untuk i bernilai [ n^(0.5), n].
• Pengecekan untuk faktor genap cukup di awal, dicek dengan angka 2. Karena untuk semua bilangan, faktor prima yang menyebabkan suatu angka bernilai genap adalah 2. Sehingga, pengecekan (nilai i) selanjutnya hanya perlu mulai dari 3, 5, 7, 9, dst. (lompat dua-dua).

Sehingga, source code [lebih] optimal:

function trial_div ( x : integer ) : boolean;
var
  i : integer;
begin
  trial_div := true;
  if ( x <> 2 ) and ( x mod 2 = 0 ) then trial_div := false
  else
  begin
    i := 3;
    while ( i <= sqrt(x) ) do
    begin
      if ( x mod i = 0 ) then
      begin
        trial_div := false;
        break;
      end;
      i := i + 2;
    end;
  end;
end;

Faktorisasi Prima
Faktorisasi prima adalah dekomposisi suatu bilangan komposit (bilangan non-prima) menjadi bilangan-bilangan prima yang lebih kecil, di mana bila semua bilangan prima tersebut dikalikan, menghasilkan bilangan semula kembali.
Contoh, 27 = 3³
Contoh lain, 48 = 2³ x 3

Prime Generating
Maksud dari prime generating adalah, meng-outputkan atau menemukan bilangan-bilangan prima dalam suatu range.
Sieve adalah algoritma yang cukup cepat untuk mencari suatu bilangan prima.
Sieve yang paling sering (dan sederhana) digunakan adalah Sieve of Eratosthenes.

Sieve of Eratosthenes

Prosedur dari Sieve of Eratosthenes:

1. Buat daftar bilangan dari 2 sampai dengan batasan tertentu.
2. Let p = 2, p adalah bilangan prima pertama.
3. Mulai dari bilangan z = p*p sampai dengan k*p, dimana k*p  adalah bilangan terbesar yang lebih kecil dari batasan, tandai bahwa z bilangan bukan prima.
4. Ambil nilai p  lain, yaitu nilai/bilangan yang belum ditandai sebagai bukan prima. Jika tidak ada lagi, selesai. Jika masih ada nilai p yang memenuhi, ulang ke langkah 3.

Source Code (pascal), array isprime[x] akan berisi nilai TRUE apabila x prima, dan FALSE apabila x komposit:

const
  batas = 1000;

var
  isprime : array [1..batas] of boolean;
  c,i     : longint;

begin
  for i := 2 to batas do
    isprime[i] := true;

  for i := 2 to batas do
    if (isprime[i] = true) then
    begin
      c := i*i;
      while (c <= batas) do
      begin
        isprime[c] := false;
        c := c + i;
      end;
    end;

  //printing primes from 2..batas
  for i := 2 to batas do
    if (isprime[i] = true) then
      writeln(i);
end.

Some interesting formulas/facts involving primes:
Banyaknya faktor dari suatu bilangan:
Bila faktorisasi prima dari suatu bilangan N = ai x bj x ... x ck, maka banyaknya pembagi/faktor dari bilangan tersebut adalah:



Jumlah dari seluruh faktor suatu bilangan:
Bilangan N = 20, memiliki banyak pembagi 6, yaitu {1,2,4,5,10,20}. Jumlah dari pembagi-pembagi tersebut adalah 42. Hal ini juga dapat dihitung dengan bantuan faktor prima dari N. JikaN = ai x bj x ... x ck, maka jumlah dari seluruh pembagi N adalah:



Mencari banyaknya bilangan x < n, yang coprime dengan n:
Cara untuk mencari banyaknya x adalah, dengan mencoba semua bilangan x dalam range [ 1, n-1 ]. Apabila fpb( x, n ) = 1, maka nilai counter ditambah 1. Algoritma ini lambat untuk nilai n yang besar.
Algoritma yang lebih baik menggunakan fungsi Euler's Phi (Totient). EulerPhi(n) dinyatakan sebagai berikut:



Misal, kita ingin mencari nilai dari EulerPhi(20), maka



Ke-delapan angka tersebut adalah {1,3,7,9,11,13,17,19}.

Wilson's Theorem:
Teorema Wilson berkata, bahwa sebuah bilangan asli p>1 merupakan bilangan prima, iff: