ALGORITMA PENCARIAN BILANGAN PRIMA

Algoritma Sieve Of Eratosthenes

Eratosthenes (276-194 S.M) adalah petugas perpustakaan ketiga dari perpustakaan terkenal di Alexandria dan adalah seorang sarjana yang sangat hebat. Eratosthenes dikenang dengan pengukurannya terhadap keliling dari dari bumi, memperkirakan jarak antara bumi dengan matahari dan bulan, dan, dalam matematika, untuk penemuan dari sebuah algoritma untuk mencari bilangan-bilangan prima, yang dikenal sebagai Algoritma Sieve Of Eratosthenes.

Sieve Of Eratosthenes adalah sebuah algoritma klasik untuk menemukan seluruh bilangan prima sampai ke sebuah N yang ditentukan. Mulai dengan array of integer yang belum dicoret dari 2 ke N. Integer pertama yang belum dicoret yaitu 2, adalah bilangan prima pertama. Coret seluruh kelipatan dari bilangan prima ini. Ulangi pada integer selanjutnya yang belum

dicoret.

Sebagai contoh, berikut adalah array pada awalnya:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

Karena 2 belum dicoret, maka 2 adalah bilangan 2 pertama kita. Kita coret seluruh kelipatan 2, yaitu 4, 6, 8, 10, 12, dst.

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

Integer selanjutnya yang belum dicoret adalah 3, maka 3 adalah prima dan kita coret seluruh kelipatan 3, seperti 6, 9. 12, dst.

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

5 adalah bilangan prima selanjutnya dan kita mencoret seluruh kelipatan 5. Satu-satunya bilangan yang dicoret dalam range ini adalah 25.

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

Maka kita mendapatkan bilangan prima selanjutnya yaitu

7, 11, 13, 17, 19, dan 23.

Kode dalam pseudocode adalah:

// tentukan batas
limit ← 1.000.000
// set semua bilangan dengan true
is_prime(i) ← true, i _ [2, limit]
for n in [2, √limit]:
if is_prime(n):
is_prime(i) ← false,
i _ {n², n²+n, n²+2n, ..., limit}
for n in [2, limit]:
if is_prime(n): print n
atau lebih sederhananya
limit = 1000000
sieve$ = string "P" with batas panjang
prime = 2
repeat while prime2 < limit
set karakter pada index dari setiap
kelipatan bilangan prima (di luar bilangan
tersebut *1) dalam sieve$ menjadi “n”
prime = index dari setiap “p” dalam sieve
$
end repeat
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
About these ads

2 thoughts on “ALGORITMA PENCARIAN BILANGAN PRIMA

  1. Good day I was luck to seek your blog in wordpress
    your subject is outstanding
    I obtain a lot in your blog really thanks very much
    btw the theme of you blog is really quality
    where can find it

Berikan Balasan

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

WordPress.com Logo

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

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s