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:
1 Comments
