. .

TUGAS & LATIHAN: Bahasa Pemrograman JAVA Netbeans IDE - Mencari Bilangan Prima Menggunakan Saringan Eratosthenes - Method sieve()

Posted by CHRISTIANTO D,WIBOWO | D3MI-2016 STMIK BUMI GORA On Selasa, Desember 13, 2016 No comments

What is Sieve Of Eratosthenes , Apa itu yah ?
Sieve Of Eratosthenes = Saringan Eratosthenes. 
Saringan Eratosthenes adalah suatu cara untuk menemukan semua bilangan prima di antara 1 sampai dengan bilangan bulat yang ditentukan "n". Saringan ini ditemukan oleh Eratosthenes, seorang ilmuwan Yunani kuno. Cara ini merupakan cara paling sederhana dan paling cepat untuk menemukan bilangan prima, sebelum Saringan Atkin ditemukan pada tahun 2004.
Saringan Atkin merupakan cara yang lebih cepat namun lebih rumit dibandingkan dengan Saringan 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.
Saringan Eratosthenes dalam Pemrograman
Saringan Eratosthenes dapat dimanfaatkan dalam pemrograman. Sebuah program dapat menampilkan deretan bilangan prima yang ada di antara 1 sampai n dengan memanfaatkan ide saringan 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");
Source : https://id.wikipedia.org/wiki/Saringan_Eratosthenes
TUGAS dan LATIHAN kali ini, Buatlah Java Program yang mampu mencari bilangan prima dari 1 sampai dengan bilangan tertentu yang diinput oleh user (Bukan Mencontoh Souce Code Diatas !!!).
Algoritmanya : Jika kita ingin menghitung semua bilangan prima hingga x, maka pertama menuliskan angka dari 2 sampai x. Hapus nomor pertama dari daftar ini (katakanlah y) dan menambahkannya ke daftar bilangan prima. Cari semua kelipatan y (tidak termasuk y) kurang dari atau sama dengan x dan menghapus mereka dari daftar. Ulangi proses di atas sampai dengan tidak ada nomor tersisa.
Kita menggambarkan prosedur ini dengan mencari semua bilangan prima kurang dari 15. (Untuk menunjukkan penghapusan item dari daftar, kita hanya menelitik keluar dan untuk menunjukkan penambahan nomor dari daftar bilangan prima, kita menempatkan tanda centang di atasnya).
Pertama, kita menuliskan semua nomor dari 2 sampai 15.
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Iterasi 1:
Pilih nomor pertama, 2. kelipatan 2 kurang dari atau sama dengan 15 adalah 4, 6, 8, 10, 12 dan 14. Kita menelitik mereka untuk menunjukkan bahwa mereka tidak bilangan prima dan menandai 2 sebagai angka pertama dengan meberi tanda centang di atasnya.
2
3
4 X
5
6 X
7
8 X
9
10 X
11
12 X
13
14 X
15
Iterasi 2:
Sekarang, kita pilih nomor berikutnya, 3. Kita mencoret kelipatan 3 kurang dari atau sama dengan 15 yang - 6, 9, 12, 15. Perhatikan bahwa 6 dan 12 telah dicoret. Jika kita ingin, kita dapat menelitik mereka lagi. Itu tidak akan membuat perbedaan apapun untuk hasil akhir tapi tidak perlu melakukannya. Namun, ketika kita melaksanakan program di Java, kita akan melihat bahwa kita mencoret angka-angka ini untuk kedua kalinya (dengan menetapkan bendera/flag/tanda salah - false yang pada angka item yang sudah salah - false), cara yang lebih sederhana dari yang pertama memeriksa jika sudah menelitik (bendera/flag/tanda sudah diatur ke false). Kita juga menempatkan tanda centang pada 3 untuk menunjukkan bahwa itu adalah bilangan prima.
2
3
4 X
5
6 X
7
8 X
9 X
10 X
11
12 X
13
14 X
15 X
Iterasi 3:
Jumlah 5 dipilih. Kelipatan dari 5 10 dan 15 yang sudah diperiksa. 5 ditandai sebagai prima.
2
3
4 X
5
6 X
7
8 X
9 X
10 X
11
12 X
13
14 X
15 X
Iterasi 4:
7 dipilih. Di sini angka 14 sudah diperiksa. jadi  angka 7 ditandai sebagai bilangan prima.
2
3
4 X
5
6 X
7
8 X
9 X
10 X
11
12 X
13
14 X
15 X
Iterasi 5: 
11 dipilih. Tidak memiliki kelipatan hingga 15. 11 ditandai sebagai bilangan prima.
2
3
4 X
5
6 X
7
8 X
9 X
10 X
11
12 X
13
14 X
15 X
Iterasi 6:
13 dipilih. Seperti yang terjadi dengan 11, 13 juga tidak memiliki kelipatan dalam daftar sebagai bilangan prima.
2
3
4 X
5
6 X
7
8 X
9 X
10 X
11
12 X
13
14 X
15 X

Tidak ada lagi nomor yang tersisa. Jadi, proses berhenti. Kita telah memperoleh 2, 3, 5, 7, 11 dan 13 sebagai bilangan prima hingga 15.

Method sieve() menerima parameter n keatas yang merupakan bilangan prima yang harus dihitung. Kita membuat boolean nama array yang merupkan bilangan prima dengan ukuran (n + 1) dan mengatur semua nilai-nilai (kecuali 0 dan 1), kita mempertimbangkan semua nomor dari 0 sampai n sebagai bilangan prima (ditunjukkan oleh nilai boolean true) Sebagai hasil eksekusi, ketentuan benar/true atau salah/false akan berubah ke salah/false semua, untuk menunjukkan bahwa mereka tidak (belum) bilangan prima. bilangan prima [i] memberitahu kita apakah jumlah i adalah prime atau tidak.

Kita akan memiliki variabel num untuk menahan/memegang angka-angka tersebut, saat kami sedang mempertimbangkan angka yang kelipatan yang sedang kita cari tahu. num awalnya diatur ke 2.

while loop - Loop sementara memiliki dua bagian.
Pada bagian pertama, kita menemukan semua kelipatan num hingga n dan mengatur bilangan prima [beberapa] ke false. Kelipatan ditemukan oleh dikalikan jumlah num dengan 2, 3, 4 ... dalam untuk loop. Jika beberapa diperoleh kurang dari n, maka ada dalam daftar yang sedang kita pertimbangkan dan jadi kita menetapkan bilangan prima [beberapa] ke false (sementara). Jika tidak, maka itu berarti bahwa, kita telah menyeberangi batas n dan begitu, kita keluar dari loop.
Pada bagian kedua, kita menemukan angka-angka yang kita akan pertimbangkan dalam iterasi berikutnya dari while loop - loop sementara yaitu kita menemukan nilai baru untuk num. Untuk melakukannya, kita gunakan untuk loop dengan loop counter, mulai dari num + 1 ke n (inklusif) dan memeriksa apakah bilangan prima [i] benar. Jika demikian, nilai berikutnya untuk num. Pada akhir loop jika tidak ada lagi nilai yang ditemukan num (ditunjukkan dengan nilai false untuk variabel nextNumFound), maka itu berarti bahwa kita telah selesai memeriksa semua nomor dan selanjutnya kita  keluar dari untuk loop.

Dari algoritma dan iterasi yang sudah dijabarkan, maka sekarang kita membuat Java Program-nya :
// @uthor CHRISTIANTO "GEMBLONG" DHARMA WIBOWO LEARN JAVA
package sieveoferatosthenes;
import java.util.Scanner;
public class SieveOfEratosthenes {

    public void primes(int n) {
       boolean[] primes = new boolean[n + 1];
       for (int i = 2; i < primes.length; i++) {
           primes[i] = true;
       }
       int num = 2;
       while (true) {
           for (int i = 2;; i++) {
               int multiple = num * i;
               if (multiple > n) {
                   break;
               } else {
                   primes[multiple] = false;
               }
           }
           boolean nextNumFound = false;
           for (int i = num + 1; i < n + 1; i++) {
               if (primes[i]) {
                   num = i;
                   nextNumFound = true;
                   break;
               }
           }
           if (!nextNumFound) {
               break;
           }
       }
       for (int i = 0; i < primes.length; i++) {
           if (primes[i]) {
               System.out.println(i);
           }
       }
   }

   public static void main(String[] args) {
System.out.println("CHRISTIANTO 'GEMBLONG' DHARMA WIBWO LEARN JAVA");
System.out.println("MENCARI BILANGAN PRIMA");
System.out.println("----------------------");
       Scanner scanner = new Scanner(System.in);
       System.out.print("Masukkan Angka (>=1): ");
       int n = scanner.nextInt();
       SieveOfEratosthenes sieve = new SieveOfEratosthenes();
       sieve.primes(n);
    }
 
}

Selesai, saya sangat menganjurkan agar membaca penjelasan dari sumber pemecahan masalah Tugas dan Latihan ini, detail pada sumber ini lebih lengkap jelas dengan banyak penjabaran yang sangat terinci : Sieve of Eratosthenes - https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes.

Terimakasih pada sumber Tugas dan Latihan ini :
  1. Sieve of Eratosthenes - http://www.javawithus.com/programs/sieve-of-eratosthenes
  2. Sieve of Eratosthenes - https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
  3. Saringan Eratosthenes - https://id.wikipedia.org/wiki/Saringan_Eratosthenes

0 komentar:

Posting Komentar