Java Program untuk Memeriksa Bilangan Prima Beserta Contoh

Apa itu Bilangan Prima?

Bilangan prima adalah bilangan asli yang lebih besar dari 1 yang hanya habis dibagi 1 atau dirinya sendiri. Misalnya, 11 hanya habis dibagi 1 atau dirinya sendiri. Bilangan prima lainnya adalah 2, 3, 5, 7, 11, 13, 17, dan urutannya terus berlanjut tanpa akhir.

Bilangan yang lebih besar dari 1 tetapi bukan bilangan prima disebut bilangan komposit, karena dapat dibentuk dari faktor-faktor yang lebih kecil. Nilai 9 adalah bilangan komposit karena habis dibagi 3, dan 15 adalah bilangan komposit karena habis dibagi 3 dan 5.

Catatan: 0 dan 1 bukanlah bilangan prima. 2 adalah satu-satunya bilangan prima genap, dan nilai negatif tidak pernah dianggap sebagai bilangan prima.

Cara Memeriksa Apakah Suatu Bilangan Adalah Bilangan Prima di Java

Strategi verifikasinya adalah uji keterdivisian yang sederhana. Ambil nilai kandidat, bagi dengan setiap bilangan bulat yang lebih kecil secara berg順番, dan periksa sisa yang dikembalikan oleh operator modulus. Sisa nol membuktikan bahwa ada pembagi, yang secara otomatis mendiskualifikasi angka tersebut.

Logika Program:

• Kita perlu membagi sebuah angka masukan, misalnya 17, dengan angka-angka dari 2 hingga 17 dan memeriksa sisanya. Jika sisanya adalah 0, angka tersebut bukan bilangan prima.
• Tidak ada suatu bilangan yang habis dibagi lebih dari setengah bilangan itu sendiri. Jadi kita perlu melakukannya lingkaran melalui saja numberToCheck/2Jika inputnya 17, setengahnya adalah 8.5 dan loop akan berulang melalui nilai 2 hingga 8.
• Jika numberToCheck habis dibagi oleh angka lain, flag isPrime diatur ke false dan loop keluar.

Dua Java Fitur-fitur tersebut menjalankan keseluruhan algoritma. Operator modulus % mengembalikan sisa dari pembagian bilangan bulat, dan break Pernyataan tersebut menghentikan perulangan segera setelah jawabannya diketahui, sehingga tidak ada iterasi yang tidak perlu dijalankan.

Java Program untuk Memeriksa Apakah Suatu Bilangan Merupakan Bilangan Prima atau Bukan

Program di bawah ini menetapkan nilai 17 ke variabel numberToCheck dan mencetak setiap langkah pembagian, sehingga Anda dapat mengikuti alur pemikiran baris demi baris. Kode ini dapat diedit, jadi ubah nilainya dan jalankan lagi dengan bilangan komposit seperti 21 untuk melihat hasil yang berlawanan.

public class PrimenumberToCheckCheck {

 public static void main(String[] args) {
  int remainder;
  boolean isPrime=true;
  int numberToCheck=17; // Enter the number you want to check for prime

  //Loop to check whether the number is divisible by any number other than 1 and itself
  for(int i=2;i<=numberToCheck/2;i++)
  {
   //number is divided by i
            remainder=numberToCheck%i;
            System.out.println(numberToCheck+" Divided by "+ i + " gives a remainder "+remainder);

       //if remainder is 0 then the number is not prime and we break the loop. Else continue the loop
     if(remainder==0)
     {
        isPrime=false;
        break;
     }
  }
  // Check value true or false, if isPrime is true then the number is prime otherwise not prime
  if(isPrime)
     System.out.println(numberToCheck + " is a Prime number");
  else
     System.out.println(numberToCheck + " is not a Prime number");
    }
  }

Output yang Diharapkan:

17 Divided by 2 gives a remainder 1
17 Divided by 3 gives a remainder 2
17 Divided by 4 gives a remainder 1
17 Divided by 5 gives a remainder 2
17 Divided by 6 gives a remainder 5
17 Divided by 7 gives a remainder 3
17 Divided by 8 gives a remainder 1
17 is a Prime number

Perulangan berhenti di angka 8 karena 17 dibagi 2 sama dengan 8 dalam aritmatika bilangan bulat. Karena tidak pernah ada sisa nol, flag isPrime mempertahankan nilai awalnya yaitu true dan kondisi terakhir mencetak hasil positif.

Pemeriksaan Bilangan Prima yang Dioptimalkan Menggunakan Metode Akar Kuadrat

Membagi hingga setengah dari angka tersebut memang benar tetapi boros. Jika suatu angka n memiliki pembagi yang lebih besar dari akar kuadratnya, maka pembagi pendamping yang sesuai harus lebih kecil dari akar kuadratnya, sehingga seharusnya sudah ditemukan. Oleh karena itu, memeriksa hingga √n menghasilkan jawaban yang sama dengan iterasi yang jauh lebih sedikit.

public class PrimeCheckOptimized {

    public static boolean isPrime(int n) {
        // 0, 1 and negative values are never prime
        if (n <= 1) {
            return false;
        }
        // 2 is the only even prime number
        if (n == 2) {
            return true;
        }
        if (n % 2 == 0) {
            return false;
        }
        // test only odd divisors up to the square root
        for (int i = 3; i * i <= n; i += 2) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        int[] samples = {1, 2, 9, 17, 97};
        for (int value : samples) {
            System.out.println(value + " is prime: " + isPrime(value));
        }
    }
}

Keluaran:

1 is prime: false
2 is prime: true
9 is prime: false
17 is prime: true
97 is prime: true

Kondisi i * i <= n Ini menghindari panggilan floating point ke Math.sqrt, dan langkah 2 melewati setiap pembagi genap. Untuk nilai seperti 1,000,003, loop dasar melakukan sekitar 500,000 iterasi sementara versi ini melakukan kurang dari 500 iterasi.

Periksa Bilangan Prima yang Dimasukkan oleh Pengguna

Input yang dikodekan secara langsung (hard-coded) memang nyaman untuk demonstrasi, namun latihan sebenarnya biasanya meminta input dari keyboard. Kelas Scanner membaca bilangan bulat dari konsol dan meneruskannya ke metode isPrime yang sama.

import java.util.Scanner;

public class PrimeCheckUserInput {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter a number: ");
        int number = sc.nextInt();

        boolean isPrime = number > 1;
        for (int i = 2; i * i <= number; i++) {
            if (number % i == 0) {
                isPrime = false;
                break;
            }
        }

        System.out.println(number + (isPrime ? " is a Prime number" : " is not a Prime number"));
        sc.close();
    }
}

Contoh Eksekusi:

Enter a number: 29
29 is a Prime number

Kesalahan Umum Saat Menulis Program Bilangan Prima

Sebagian besar kesalahan pengiriman kode terjadi karena nilai batas, bukan karena loop utama. Daftar di bawah ini mencakup kesalahan yang paling sering muncul dalam kode pemula.

1. Memulai perulangan dari 1: Setiap bilangan bulat dapat dibagi 1, sehingga flag langsung diatur ke false dan program melaporkan bahwa tidak ada bilangan prima.
2. Menganggap 1 sebagai bilangan prima: Nilai 1 hanya memiliki satu pembagi, sehingga tidak memenuhi definisi dua pembagi dan harus mengembalikan nilai false.
3. Menghilangkan pernyataan break: Program tersebut tetap memberikan jawaban yang benar, tetapi terus berulang setelah keputusannya diketahui, yang membuang waktu pada input yang besar.
4. Menggunakan i <= n sebagai batasnya: Angka tersebut selalu dapat dibagi oleh dirinya sendiri, jadi perulangan harus berhenti sebelum mencapai n.
5. Membandingkan dengan = alih-alih ==: Tanda sama dengan tunggal memberikan nilai alih-alih mengujinya, yang menghasilkan kesalahan kompilasi pada kondisi if.

Perbandingan Metode Pemeriksaan Bilangan Prima

Pilih metode yang sesuai dengan ukuran input dan apakah satu nilai atau seluruh rentang nilai yang perlu diuji.

Ketika seluruh rentang nilai harus diklasifikasikan, bukan hanya satu nilai, maka metode penyaringan jauh lebih efisien. Program pendamping kami untuk menemukan Perdana Numbers dari 1 ke 100 Hal ini menunjukkan pola tersebut. Untuk latihan berbasis perulangan yang terkait, tinjau kembali Deret Fibonacci dalam Java, yang Java program palindrom, Dan Bubble Sortir algoritma dalam JavaPara pemula yang membutuhkan penyegaran tentang cara mendeklarasikan bendera dan penghitung sebaiknya membaca tentang... Java variabel di utama Java tutorial.

Pertanyaan Umum Demo Slot