ALGORITMA PENCARIAN BILANGAN PRIMA

Algoritma Brute Force

Tidak ada tetapan dalam pencarian bilangan prima menggunakan algoritma Brute Force. Algoritma di bawah ini adalah algoritma Brute Force (cara naif) dan merupakan algoritma yang sederhana.

 

Pertama-tama kita membuat suatu list yang akan diisi dengan bilangan prima yang kita dapatkan. Pada awalnya di dalam list tersebut tidak ada bilangan lain selain 3. Kemudian kita akan mengecek seluruh bilangan ganjil sampai dengan batas yang telah kita tentukan sendiri, dan membandingkannya dengan bilangan prima yang ada dalam list bilangan prima tadi. Jika bilangan tersebut tidak bisa dibagi oleh seluruh bilangan prima yang ada dalam list maka bilangan tersebut adalah bilangan prima dan kita bisa menambahkannya ke dalam list bilangan prima tadi. Pada akhirnya kita harus menambahkan angka 2 ke dalam list tersebut. Satu hal lainnya yang patut dicatat, kita hanya harus mengecek bilangan prima sampai akar kuadrat dari

batas nilai dari list tersebut.

 

Hal ini terlihat baik, sebagai sebuah pendekatan kasar terhadap fungsi perhitungan bilangan prima adalah x/ln x, dan kita hanya perlu mengecek bilangan prima sampai √(n). Secara

kasar kita harus melakukan paling banyak √(n)/ln√(n) tes terhadap suatu angka untuk menentukan dengan keakuratan 100% bahwa bilangan tersebut adalah prima. Fungsi ini memang

akan memakan waktu yang lama, tapi pada kenyataannya tidak teralalu lama. Berikut kodenya dalam pseudocode:

 

procedure deterministicPrimeSeqence(end):
if end < 2: return []
if end < 3: return [2]
primes = [3]
for i in range(5,end,2):
sqt = int(sqrt(i))
for prime in primes:
if prime > sqt:
primes.append(i)
break
if i%prime == 0: break
primes.insert(0,2)
return primes

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s