Tapis Eratosthenes: Perbedaan antara revisi
Tidak ada ringkasan suntingan |
Dedhert.Jr (bicara | kontrib) Tidak ada ringkasan suntingan |
||
(11 revisi perantara oleh 7 pengguna tidak ditampilkan) | |||
Baris 1: | Baris 1: | ||
{{Tanpa referensi|date=Januari 2022}}[[Berkas:Sieve_of_Eratosthenes_animation.gif|jmpl|ka|500px|Animasi tapis Eratosthenes dari 1 sampai ''n''=120. Daftar A (kiri) dan daftar B (kanan). Bilangan yang sudah diwarnai artinya sudah dicoret.]] |
|||
bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajobajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz tz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajobajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz tz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajobajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz tz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajobajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz tz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajobajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz tz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajobajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz tz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajobajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz tz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajobajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz tz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajobajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz tz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajobajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz bajotz tz |
|||
'''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''. |
|||
# 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. |
|||
== Tapis Eratosthenes dalam Pemrograman == |
|||
Tapis Eratosthenes dapat dimanfaatkan dalam [[pemrograman komputer|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 (bahasa pemrograman)|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 == |
|||
* [http://primesieve.org/ primesieve - Very fast highly optimized C/C++ segmented Sieve of Eratosthenes] |
|||
* [https://www.encyclopediaofmath.org/index.php/Eratosthenes,_sieve_of ''Eratosthenes, sieve of'' at Encyclopaedia of Mathematics] |
|||
* [http://www.hbmeyer.de/eratosiv.htm Interactive JavaScript Page] |
|||
* [http://demonstrations.wolfram.com/SieveOfEratosthenes/ Sieve of Eratosthenes] by George Beck, [[Wolfram Demonstrations Project]]. |
|||
* [https://wiki.haskell.org/Prime_numbers#Sieve_of_Eratosthenes Sieve of Eratosthenes in Haskell] |
|||
* [http://www.algolist.net/Algorithms/Number_theoretic_algorithms/Sieve_of_Eratosthenes Sieve of Eratosthenes algorithm illustrated and explained. Java and C++ implementations.] |
|||
* [http://zsmith.co/primes.html A related sieve written in x86 assembly language] |
|||
* [https://sites.google.com/site/bbuhrow/home/cuda-sieve-of-eratosthenes Fast optimized highly parallel CUDA segmented Sieve of Eratosthenes in C] |
|||
* [http://c2.com/cgi/wiki?SieveOfEratosthenesInManyProgrammingLanguages SieveOfEratosthenesInManyProgrammingLanguages c2 wiki page] |
|||
* [http://wwwhomes.uni-bielefeld.de/achim/prime_sieve.html The Art of Prime Sieving] Sieve of Eratosthenes in C from 1998 with nice features and algorithmic tricks explained. |
|||
<!--spacing--> |
|||
{{DEFAULTSORT:Sieve Of Eratosthenes}} |
|||
[[Kategori:Uji primaliti]] |
|||
[[Kategori:Artikel dengan contoh kodesemu]] |
|||
[[Kategori:Teori Saringan| ]] |
|||
[[Kategori:Algoritma]] |
Revisi terkini sejak 22 Januari 2022 07.17
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
[sunting | sunting sumber]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.
Tapis Eratosthenes dalam Pemrograman
[sunting | sunting sumber]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
[sunting | sunting sumber]- primesieve - Very fast highly optimized C/C++ segmented Sieve of Eratosthenes
- Eratosthenes, sieve of at Encyclopaedia of Mathematics
- Interactive JavaScript Page
- Sieve of Eratosthenes by George Beck, Wolfram Demonstrations Project.
- Sieve of Eratosthenes in Haskell
- Sieve of Eratosthenes algorithm illustrated and explained. Java and C++ implementations.
- A related sieve written in x86 assembly language
- Fast optimized highly parallel CUDA segmented Sieve of Eratosthenes in C
- SieveOfEratosthenesInManyProgrammingLanguages c2 wiki page
- The Art of Prime Sieving Sieve of Eratosthenes in C from 1998 with nice features and algorithmic tricks explained.