Widget edited by super-bee

Laman

12.24.2010

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


Artikel Terkait:

Comments
1 Comments

1 komentar:

kita juga punya nih jurnal mengenai algoritma bruteforce, silahkan dikunjungi dan dibaca , berikut linknya
http://repository.gunadarma.ac.id/bitstream/123456789/2748/1/22-EVALUASI%20KINERJA%20ALGORITMA%20TRAVELING%20SALESMAN%20PROBLEM%20DENGAN%20TEKNIK%20PEMROGRAMAN%20DINAMIK.pdf
semoga bermanfaat yaa :)

Posting Komentar

Twitter Delicious Facebook Digg Stumbleupon Favorites More