Bilangan Prima dengan Algoritma Sieve of Eratosthenes
Bilangan prima merupakan suatu bilangan khusus dimana bilangan tersebut tidak dapat hapis dibagi oleh bilangan manapun kecuali bilangan itu sendiri dan 1. Saat ini banyak algoritma yang dapat digunakan untuk menentukan suatu bilangan termasuk prima atau bukan. Salah satu algoritma tersebut adalah Sieve of Eratosthenes, dapat kita temukan penjelasannya di Wikipedia. Mungkin ini bukan algoritma yang tercepat, tapi setidaknya sudah cukup cepat dibanding jika menggunakan modulus.
Dan berikut ini contoh penerapan algoritma di atas dalam bahasa pemrograman PHP. Script ini sudah ditest untuk menampilkan bilangan prima dibawah 1.000.000 dan berhasil menampilkannya dalam waktu 3 detik.
<?php
function bilangan_prima($limit) {
$prima = array();
for ($i=2; $i<=$limit; $i++)
$prima[$i] = true;
$akarLimit = (int)sqrt($limit);
for ($i=2; $i<=$akarLimit; $i++) {
if ($prima[$i]) {
for ($j=$i*$i; $j<=$limit; $j+=$i) {
$prima[$j] = false;
}
}
}
$i = 0;
foreach ($prima as $bilangan=>$status) {
if ($status) { echo "$bilangan ";$i++; }
}
echo "Jumlahnya:". $i;
}
$start=mktime();
bilangan_prima(1000000); //menampilkan bilangan prima dari 1 - 1 juta
$finish=mktime();
$result=$finish-$start;
echo "Time: $result seconds";
?>
Penjelasan Algoritma:
Misalkan kita hendak menemukan semua bilangan prima di antara 1 sampai suatu bilangan bulat n.
- Tulis semua bilangan, mulai dari 1 sampai n. Misalkan ini adalah daftar A.
- Buat suatu daftar yang masih kosong, sebut saja daftar B.
- Coret bilangan 1 dari daftar A.
- Lalu tulis 2 pada daftar B. Lalu coret 2 dan semua kelipatannya dari daftar A
- Bilangan pertama yang belum tercoret dari daftar A (misalnya 3) adalah bilangan prima. Tulis bilangan ini di daftar B, lalu coret bilangan ini dan semua kelipatannya dari daftar A.
- Ulangi langkah 4 sampai semua bilangan di daftar A sudah tercoret.
Setelah selesai, semua bilangan di daftar B adalah bilangan prima.
Baca Juga:
(0 votes, average: 0.00 out of 5)You need to be a registered member to rate this post.
Loading ...If you enjoyed this post, please consider to leave a comment or subscribe to the feed and get future articles delivered to your feed reader.
pusing pak baca na,, hehehe
jangan dibaca, tapi dicoba. hehe
pak itu kan kalo mau buat php di notepad
terus setelah disimpan saya mau lihat nya gmn?
soalnya saya tidak ngerti sama sekali.
itu kan seperti kita membuat hitung2n program.
terus saya dpt menjalankan program nya pake program yg lain atau tidak.
maap kalo bnyk nanya soalnya lagi tahap belakjar
thx
Assalamualaikum bapa’
Jujur salut banget sama web ini, semoga makin banyak contoh yang bisa dibaca untuk referensi. Amin
kebetulan minggu yg lalu saya dapet tugas kuliah
buat algoritma untuk mencari bilangan prima ke n,hahaha
bingung dan belum dapet, kalau mencetak dari sekian ke sekian sih gampang, tapi kalau kencari ke n masih belum dapet.
Sukses selalu untuk bapa’
@dwi: PHP itu bahasa pemrograman web-based, dapat ditulis murni PHP atau sebagai sisipan HTML. Karena PHP bersifat server-side scripting, maka kita membutuhkan SERVER untuk mengeksekusi PHP, dan kita dapat membuatnya di komputer kita sebagai LOCALHOST, sy menyarankan “http://www.appservnetwork.com/”
untuk belajar pemrograman lebih menyenangkan, silakan bergabung di “http://www.indo-code.com”, sampai ketemu ya..
kakak saya sudah k TKP (http://www.indo-code.com) tapi situs tersebut menampilkan pesan seperti ini “Dalam proses pengembangan.
Website off dengan batas waktu yang tidak dapat ditentukan. “. jadi kapan ka situsnya bisa diakses….terima kasih.