Rabu, 18 November 2026
08:37 WIB
TERKINI
Bandar Lampung Agenda Strategis Pemprov Lampung 6 November 2026: Revitalisasi Stadion Jadi Prioritas Bandar Lampung Harga Beras di Pasar Pasir Gintung Bandar Lampung Merangkak Naik, Stok Aman Bandar Lampung Disdag Bandar Lampung Jamin Pasokan Beras Aman hingga Akhir 2026 Insight Komitmen Pembangunan Negeri, PTBA Sabet Penghargaan Kepatuhan PNBP ESDM 2026 Pemprov Lampung Gubernur Mirza Canangkan Mulang Maya Jadi Magnet Wisata Budaya Unggulan Lampung Tuba Barat Mewujudkan Haji: Pemkab Tubaba dan BSI Ajak Masyarakat Menabung Sejak Dini Lampung Timur Bupati Ela Dekatkan Diri dengan Siswa, Pastikan Kualitas Pendidikan dan Gizi di Lampung Timur Tuba Barat Kemitraan Strategis Pemkab Tubaba dan Kejari: Wujudkan Tata Kelola Pemerintahan Akuntabel Bandar Lampung Mantan Ketua DPRD Lampung Bersaksi dalam Sidang Arinal Djunaidi Bandar Lampung Senator Bustami Zainudin dan Staf DPD Lampung Ikuti Program Cek Kesehatan Gratis Bandar Lampung Agenda Strategis Pemprov Lampung 6 November 2026: Revitalisasi Stadion Jadi Prioritas Bandar Lampung Harga Beras di Pasar Pasir Gintung Bandar Lampung Merangkak Naik, Stok Aman Bandar Lampung Disdag Bandar Lampung Jamin Pasokan Beras Aman hingga Akhir 2026 Insight Komitmen Pembangunan Negeri, PTBA Sabet Penghargaan Kepatuhan PNBP ESDM 2026 Pemprov Lampung Gubernur Mirza Canangkan Mulang Maya Jadi Magnet Wisata Budaya Unggulan Lampung Tuba Barat Mewujudkan Haji: Pemkab Tubaba dan BSI Ajak Masyarakat Menabung Sejak Dini Lampung Timur Bupati Ela Dekatkan Diri dengan Siswa, Pastikan Kualitas Pendidikan dan Gizi di Lampung Timur Tuba Barat Kemitraan Strategis Pemkab Tubaba dan Kejari: Wujudkan Tata Kelola Pemerintahan Akuntabel Bandar Lampung Mantan Ketua DPRD Lampung Bersaksi dalam Sidang Arinal Djunaidi Bandar Lampung Senator Bustami Zainudin dan Staf DPD Lampung Ikuti Program Cek Kesehatan Gratis
Tapis Eratosthenes

Tapis Eratosthenes

Bagikan:
60px-Question_book-new.svg.png?utm_source=id.wikipedia.org&utm_campaign=parser&utm_content=thumbnail
Artikel ini tidak memiliki referensi atau sumber tepercaya sehingga isinya tidak bisa dipastikan. Tolong bantu perbaiki artikel ini dengan menambahkan referensi yang layak. Tulisan tanpa sumber dapat dipertanyakan dan dihapus sewaktu-waktu.
Cari sumber: "Tapis Eratosthenes" – berita · surat kabar · buku · cendekiawan · JSTOR
Sieve_of_Eratosthenes_animation.gif?utm_source=id.wikipedia.org&utm_campaign=parser&utm_content=thumbnail_unscaled
Animasi tapis Eratosthenes dari 1 sampai n=120. Daftar A (kiri) dan daftar B (kanan). Bilangan yang sudah diwarnai artinya sudah dicoret.

Tapis Eratosthenes adalah suatu cara untuk menemukan semua bilangan prima di antara 1 dan suatu angka n. Tapis ini ditemukan oleh Eratosthenes, seorang ilmuwan Yunani kuno. Cara ini merupakan cara paling sederhana dan paling cepat untuk menemukan bilangan prima, sebelum Tapis Atkin ditemukan pada tahun 2004. Tapis Atkin merupakan cara yang lebih cepat tetapi lebih rumit dibandingkan dengan Tapis Eratosthenes.

Langkah-langkah tapis Eratosthenes

Misalkan kita hendak menemukan semua bilangan prima di antara 1 sampai suatu bilangan bulat n.

  1. Tulis semua bilangan, mulai dari 1 sampai n. Misalkan ini adalah daftar A.
  2. Buat suatu daftar yang masih kosong, sebut saja daftar B.
  3. Coret bilangan 1 dari daftar A.
  4. Lalu tulis 2 pada daftar B. Lalu coret 2 dan semua kelipatannya dari daftar A
  5. 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.
  6. Ulangi langkah 4 sampai semua bilangan di daftar A sudah tercoret.

Setelah selesai, semua bilangan di daftar B adalah bilangan prima.

Tapis Eratosthenes dalam Pemrograman

Tapis Eratosthenes dapat dimanfaatkan dalam pemrograman. Sebuah program dapat menampilkan deretan bilangan prima yang ada di antara 1 sampai n dengan memanfaatkan ide tapis Eratosthenes. Berikut ini adalah sebuah potongan kode dalam bahasa pemrograman Java dan C yang mencetak bilangan prima di antara 1 sampai n=120.

int n=120; //batas atas n dapat diganti dengan bilangan bulat lainnya
boolean[] prima=new boolean[n+1];

for(int i=0; i<=n; i++)
	prima[i]=true;        //set seluruh array menjadi true
prima[0]=prima[1]=false;     //0 dan 1 bukan bil. prima
double akarN=Math.sqrt(n);      //akar kuadrat dari n

//coret bilangan yang bukan prima
for(int i=2; i<=akarN; i++) {
	if (prima[i]) {
	     for (int j=i*i; j<=n; j=j+i)
                 prima[j]=false;
	}
}

//tampilkan seluruh bilangan prima
for(int i=0; i<n; i++) {
	if (prima[i])
		System.out.print(i+ "\t");

Pranala luar

Konten disalin dari Wikipedia Bahasa Indonesia (lisensi CC BY-SA) Lihat versi asli di Wikipedia

Rekomendasi Pilihan