Menghasilkan Bilangan Prima di Jawa

1. Perkenalan

Dalam tutorial ini, kami akan menunjukkan berbagai cara untuk menghasilkan bilangan prima menggunakan Java.

Jika Anda ingin memeriksa apakah suatu bilangan prima - berikut panduan singkat tentang cara melakukannya.

2. Bilangan prima

Mari kita mulai dengan definisi inti. Bilangan prima adalah bilangan asli yang lebih besar dari bilangan yang tidak memiliki pembagi positif selain satu dan dirinya sendiri.

Misalnya, 7 adalah bilangan prima karena 1 dan 7 adalah satu-satunya faktor bilangan bulat positifnya, sedangkan 12 bukan karena memiliki pembagi 3 dan 2 selain 1, 4, dan 6.

3. Menghasilkan Bilangan Prima

Di bagian ini, kita akan melihat bagaimana kita dapat menghasilkan bilangan prima secara efisien yang lebih rendah dari nilai yang diberikan.

3.1. Java 7 dan Sebelumnya - Brute Force

public static List primeNumbersBruteForce(int n) { List primeNumbers = new LinkedList(); for (int i = 2; i <= n; i++) { if (isPrimeBruteForce(i)) { primeNumbers.add(i); } } return primeNumbers; } public static boolean isPrimeBruteForce(int number) { for (int i = 2; i < number; i++) { if (number % i == 0) { return false; } } return true; } 

Seperti yang Anda lihat, primeNumbersBruteForce melakukan iterasi pada angka dari 2 ke n dan hanya memanggil metode isPrimeBruteForce () untuk memeriksa apakah suatu bilangan prima atau tidak.

Metode ini memeriksa setiap angka yang dapat dibagi dengan angka dalam rentang dari 2 hingga angka-1 .

Jika suatu saat kami menemukan angka yang habis dibagi, kami mengembalikan salah. Pada akhirnya ketika kita menemukan bahwa bilangan tersebut tidak habis dibagi dengan bilangan sebelumnya, kita mengembalikan true yang menunjukkan bilangan prima.

3.2. Efisiensi dan Optimasi

Algoritma sebelumnya tidak linier dan memiliki kompleksitas waktu O (n ^ 2). Algoritme juga tidak efisien dan jelas ada ruang untuk perbaikan.

Mari kita lihat kondisi dalam metode isPrimeBruteForce () .

Jika suatu bilangan bukan bilangan prima, bilangan ini dapat difaktorkan menjadi dua faktor yaitu a dan b yaitu bilangan = a * b. Jika a dan b lebih besar dari akar kuadrat dari n , a * b akan lebih besar dari n .

Jadi setidaknya salah satu faktor tersebut harus kurang dari atau sama dengan akar kuadrat dari sebuah bilangan dan untuk memeriksa apakah sebuah bilangan prima, kita hanya perlu menguji faktor yang lebih rendah dari atau sama dengan akar kuadrat dari bilangan yang diperiksa.

Bilangan prima tidak pernah bisa menjadi bilangan genap karena semua bilangan genap dapat dibagi 2.

Selain itu, bilangan prima tidak pernah bisa menjadi bilangan genap karena semua bilangan genap habis dibagi 2.

Dengan mengingat ide-ide di atas, mari tingkatkan algoritme:

public static List primeNumbersBruteForce(int n) { List primeNumbers = new LinkedList(); if (n >= 2) { primeNumbers.add(2); } for (int i = 3; i <= n; i += 2) { if (isPrimeBruteForce(i)) { primeNumbers.add(i); } } return primeNumbers; } private static boolean isPrimeBruteForce(int number) { for (int i = 2; i*i < number; i++) { if (number % i == 0) { return false; } } return true; } 

3.3. Menggunakan Java 8

Mari kita lihat bagaimana kita dapat menulis ulang solusi sebelumnya menggunakan idiom Java 8:

public static List primeNumbersTill(int n) { return IntStream.rangeClosed(2, n) .filter(x -> isPrime(x)).boxed() .collect(Collectors.toList()); } private static boolean isPrime(int number) { return IntStream.rangeClosed(2, (int) (Math.sqrt(number))) .filter(n -> (n & 0X1) != 0) .allMatch(n -> x % n != 0); } 

3.4. Menggunakan Saringan Eratosthenes

Ada lagi metode efisien lain yang dapat membantu kita menghasilkan bilangan prima secara efisien, dan itu disebut Sieve Of Eratosthenes. Efisiensi waktunya adalah O (n logn).

Mari kita lihat langkah-langkah algoritma ini:

  1. Buat daftar bilangan bulat berurutan dari 2 hingga n : (2, 3, 4,…, n)
  2. Awalnya, misalkan p sama dengan 2, bilangan prima pertama
  3. Mulai dari p , hitung dengan kelipatan p dan tandai masing-masing angka ini lebih besar dari p itu sendiri dalam daftar. Angka-angka ini akan menjadi 2p, 3p, 4p, dll .; perhatikan bahwa beberapa di antaranya mungkin telah ditandai
  4. Temukan angka pertama yang lebih besar dari p dalam daftar yang tidak bertanda. Jika tidak ada nomor tersebut, berhentilah. Jika tidak, misalkan p sekarang sama dengan bilangan ini (yang merupakan bilangan prima berikutnya), dan ulangi dari langkah 3

Di akhir ketika algoritme berakhir, semua bilangan dalam daftar yang tidak ditandai adalah bilangan prima.

Berikut tampilan kodenya:

public static List sieveOfEratosthenes(int n) { boolean prime[] = new boolean[n + 1]; Arrays.fill(prime, true); for (int p = 2; p * p <= n; p++) { if (prime[p]) { for (int i = p * 2; i <= n; i += p) { prime[i] = false; } } } List primeNumbers = new LinkedList(); for (int i = 2; i <= n; i++) { if (prime[i]) { primeNumbers.add(i); } } return primeNumbers; } 

3.5. Contoh Pengerjaan Saringan Eratosthenes

Mari kita lihat cara kerjanya untuk n = 30.

Perhatikan gambar di atas, berikut adalah pass yang dibuat oleh algoritme:

  1. Loop dimulai dengan 2, jadi kita meninggalkan 2 tanpa tanda dan menandai semua pembagi 2. Itu ditandai dalam gambar dengan warna merah
  2. Perulangan berpindah ke 3, jadi kita meninggalkan 3 tanpa tanda dan menandai semua pembagi dari 3 yang belum ditandai. Itu ditandai dalam gambar dengan warna hijau
  3. Putaran pindah ke 4, sudah ditandai, jadi kita lanjutkan
  4. Putaran pindah ke 5, jadi kita tinggalkan 5 tanpa tanda dan tandai semua pembagi dari 5 yang belum ditandai. Itu ditandai dalam gambar dengan warna ungu
  5. Kami melanjutkan langkah-langkah di atas sampai loop tercapai sama dengan akar kuadrat dari n

4. Kesimpulan

Dalam tutorial singkat ini, kami mengilustrasikan cara-cara di mana kami dapat menghasilkan bilangan prima hingga nilai 'N'.

Penerapan contoh-contoh ini dapat ditemukan di GitHub.