Share to: share facebook share twitter share wa share telegram print page

Tapis Eratosthenes

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 namun 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

Read other articles:

Artikel ini sebatang kara, artinya tidak ada artikel lain yang memiliki pranala balik ke halaman ini.Bantulah menambah pranala ke artikel ini dari artikel yang berhubungan atau coba peralatan pencari pranala.Tag ini diberikan pada November 2022. Dmitri BobrovInformasi pribadiNama lengkap Dmitri Viktorovich BobrovTanggal lahir 5 Juli 1990 (umur 33)Tinggi 1,79 m (5 ft 10+1⁄2 in)Posisi bermain BekKarier senior*Tahun Tim Tampil (Gol)2006-2009 FC Academia Dimitrovgrad 60 (0)…

Charles Le MoyneHarry Carey dan Charles Le Moyne dalam Sundown Slim (1920)LahirCarl Jonathan Lemon(1880-06-27)27 Juni 1880Marshall, Illinois, Amerika SerikatMeninggal13 September 1956(1956-09-13) (umur 76)Hollywood, California, Amerika SerikatPekerjaanPemeranTahun aktif1915-1937 Charles Le Moyne (27 Juni 1880 – 13 September 1956) adalah seorang pemeran film Amerika Serikat dari era film bisu. Ia tampil dalam 73 film antara 1915 dan 1937. Filmografi pilihan The Princess …

Labeobarbus varicostoma Varicorhinus varicostoma TaksonomiKerajaanAnimaliaFilumChordataKelasActinopteriOrdoCypriniformesFamiliCyprinidaeGenusVaricorhinusSpesiesVaricorhinus varicostoma Tata namaSinonim takson Varicorhinus varicostoma lbs Labeobarbus varicostoma adalah sebuah spesies ikan bersirip kipas dalam genus Labeobarbus. Spesies tersebut adalah endemik di Sungai Lucalla, Angola.[1] Referensi ^ Froese, Rainer and Pauly, Daniel, eds. (2006). Labeobarbus varicostoma di situs FishBase.…

Военно-морские силы Джибутифр. Garde-Cotesсомал. Ciidanka Badda Jabuuti Годы существования 1977 — настоящее время Страна Африка Входит в Вооружённые силы Джибути Тип Военно-морской флот  Медиафайлы на Викискладе Военно-морские силы Джибути (фр. Garde-Cotes, сомал. Ciidanka Badda Jabuuti)— один …

Peta menunjukkan lokasi Jaen Data sensus penduduk di Jaen Tahun Populasi Persentase 199553.541—200058.2741.83%200763.4741.19% Jaen adalah munisipalitas yang terletak di provinsi Nueva Ecija, Filipina. Pada tahun 2010, munisipalitas ini memiliki populasi sebesar 66.293 jiwa dan 14.922 rumah tangga. Pembagian wilayah Secara administratif Jaen terbagi menjadi 27 barangay, yaitu: Calabasa Dampulan (Pob.) Hilera Imbunia Imelda Pob. (Doña Aurora) Lambakin Langla Magsalisi Malabon-Kaingin Marawa Ant…

Bahan baku Karet Bahan baku atau barang mentah adalah bahan yang dibeli dan digunakan dalam membuat produk akhir barang jadi yang akan dijual kepada konsumen. Bahan baku belum mengalami proses pengolahan sama sekali. Contoh bahan baku dalam hal makanan adalah mentega, gula, telur, tepung, vanili, bubuk pemuai, soda kue dan coklat untuk pembuatan produk coklat. Sedangkan biaya bahan baku adalah seluruh biaya untuk memperoleh sampai dengan bahan siap untuk digunakan yang meliputi harga bahan, ongk…

Cilamaya KulonKecamatanPeta lokasi Kecamatan Cilamaya KulonNegara IndonesiaProvinsiJawa BaratKabupatenKarawangPemerintahan • CamatSuryadiPopulasi • Total59,917 jiwa jiwaKode Kemendagri32.15.23 Kode BPS3215082 Luas63,18 km2Desa/kelurahan12 Cilamaya Kulon (atau disebut juga Cilamaya Barat) adalah sebuah kecamatan di Kabupaten Karawang, Provinsi Jawa Barat, Indonesia. Kecamatan Cilamaya Kulon adalah kecamatan pemecahan dari kecamatan Cilamaya yang telah berganti nama me…

La section « Histoire » de l'article « Électron » est une chronologie détaillée de l'étude expérimentale de l'électricité. La foudre, manifestation spectaculaire de l'électricité. L'électricité existe depuis les débuts de l'Univers. Son histoire vue par les hommes remonte aux débuts de l'humanité, car l'électricité est partout présente, elle est très discrète la majorité du temps mais se manifeste parfois de manière très spectaculaire et brutale …

Artikel ini sebatang kara, artinya tidak ada artikel lain yang memiliki pranala balik ke halaman ini.Bantulah menambah pranala ke artikel ini dari artikel yang berhubungan atau coba peralatan pencari pranala.Tag ini diberikan pada Desember 2022. Mozes PauseS.H. Ketua DPRD LamandauMasa jabatan2009–2014Ketua DPRD LamandauMasa jabatan2004–2009 Informasi pribadiLahir(1958-07-06)6 Juli 1958 Merambang, Kalimantan TengahMeninggal26 Maret 2015(2015-03-26) (umur 56) Nanga Bulik, LamandauKebangsa…

ChynaChyna, 2008LahirJoan Marie Laurer(1969-12-27)27 Desember 1969Rochester, New York, A.S.Meninggal17 April 2016(2016-04-17) (umur 46)Redondo Beach, California, A.S.Sebab meninggalOverdosisMakamAbu disebar ke Samudra Pasifik[1][2]AlmamaterUniversitas TampaPekerjaanPegulat profesionalmodel glamoraktrisbinaragawanPasanganTriple H (1996–2000)Sean Waltman (2003–2005)Karier gulat profesionalNama ringChyna[3]Chyna Doll[3]Joanie Laurer[3]Joanie Lee…

Javier ForésForés di Grand Prix Malaysia 2010KebangsaanSpanyolLahir16 September 1985 (umur 38)Llombai, SpanyolTim saat iniKawasaki Puccetti RacingNo. motor12 Catatan statistik Karier Kejuaraan Dunia MotoGP Tahun aktif2016 PabrikanDucati Juara dunia0Klasemen 2016NC (0 poin) Start Menang Podium Pole F. lap Poin 1 0 0 0 0 0 Karier Kejuaraan Dunia Moto2Tahun aktif2010–2011 PabrikanBimota, AJR, Suter Juara dunia0 Klasemen 2011NC (0 poin) Start Menang Podium Pole F. lap Poin 10 0 0 0 0 0 Kari…

Children's television awards show program broadcast in 2022 2022 Kids' Choice AwardsDateApril 9, 2022 (2022-04-09)LocationBarker HangarSanta Monica, CaliforniaHosted byMiranda CosgroveRob GronkowskiMost awardsSpider-Man: No Way Home and High School Musical: The Musical: The Series (3)Most nominationsAdele, Cobra Kai, Danger Force, High School Musical: The Musical: The Series, iCarly, Taylor Swift, and The SpongeBob Movie: Sponge on the Run (4)Television/radio coverageNetwork Nicke…

This is a list of launches made by the R-7 Semyorka ICBM, and its derivatives between 1980 and 1984. All launches are orbital satellite launches, unless stated otherwise. Contents 1957 1958 1959 1960 1961 1962 1963 1964 1965 1966 1967 1968 1969 1970 1971 1972 1973 1974 1975 1976 1977 1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013 2014 2015 2016 2017 2018 2019 2020 …

1999 history book by John W. Dower Embracing Defeat First edition coverAuthorJohn W. DowerCountryUnited StatesLanguageEnglishGenreHistoryPublisherW.W. Norton & Co.Publication date1999Media typePrint (hardcover)Pages676ISBN978-0-393-32027-5Preceded byThe Bombed: Hiroshima and Nagasaki in Japanese Memory, Diplomatic History 19, no. 2 Followed byCultures of War: Pearl Harbor, Hiroshima, 9-11, Iraq  Embracing Defeat: Japan in the Wake of World War II is a history book wr…

Aspect ratio of a displayed image This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Widescreen – news · newspapers · books · scholar · JSTOR (April 2008) (Learn how and when to remove this message) Classic television aspect ratio 4:3, and two wider ratios Widescreen in a control room Widescreen images are display…

Orchestre symphonique de Québec Pays de résidence Canada Ville de résidence Québec Années d'activité Depuis 1902 Type de formation Orchestre symphonique Genre Musique classique Direction Clemens Schuldt Membres fondateurs Joseph Vézina Statut OBNL Site web http://www.osq.org/ modifier  L'Orchestre symphonique de Québec (OSQ) est un orchestre symphonique basé à Québec, au Québec (Canada). Il a été fondé en 1902 et son chef principal et directeur musical est présentement Cleme…

Philosophical work by Leibniz Monadology The Monadology (French: La Monadologie, 1714) is one of Gottfried Leibniz's best known works of his later philosophy. It is a short text which presents, in some 90 paragraphs, a metaphysics of simple substances, or monads. Text The first manuscript page of the Monadology During his last stay in Vienna from 1712 to September 1714, Leibniz wrote two short texts in French which were meant as concise expositions of his philosophy. After his death, Principes d…

Digital camera model This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Canon EOS 80D – news · newspapers · books · scholar · JSTOR (October 2020) (Learn how and when to remove this message) Canon EOS 80DOverviewTypeDigital single-lens reflex cameraReleasedMarch 2016Intro priceUS$ 1,199.00LensLensInterchangeable (…

Genus of algae Nannochloropsis Nannochloropsis viewed under a light microscope Scientific classification Domain: Eukaryota Clade: Diaphoretickes Clade: SAR Clade: Stramenopiles Phylum: Gyrista Subphylum: Ochrophytina Class: Eustigmatophyceae Order: Eustigmatales Family: Monodopsidaceae Genus: NannochloropsisD.J.Hibberd, 1981[1] Type species Nannochloropsis oculata(Droop 1955) Hibberd 1981 Nannochloropsis is a genus of algae comprising six known species. The genus in the current taxonomic…

Arondisemen Blaye Administrasi Negara Prancis Region Aquitaine Departemen Gironde Kanton 4 Komune 55 Subprefektur Blaye Statistik Luas¹ 696 km² Populasi  - 1999 54,136  - Kepadatan 78/km² Lokasi Lokasi Blaye di Aquitaine ¹ Data Pendaftaran Tanah Prancis, tak termasuk danau, kolam, dan gletser lebih besar dari 1 km² (0.386 mi² atau 247 ekar) juga muara sungai. Arondisemen Blaye merupakan sebuah arondisemen di Prancis, terletak di département Gironde, di région Aquitaine.…

Kembali kehalaman sebelumnya