Java Chương trình kiểm tra số nguyên tố kèm ví dụ

Một số nguyên tố là gì?

Số nguyên tố là số tự nhiên lớn hơn 1 chỉ chia hết cho 1 hoặc chính nó. Ví dụ, 11 chỉ chia hết cho 1 hoặc chính nó. Các số nguyên tố khác là 2, 3, 5, 7, 11, 13, 17, và dãy số này còn tiếp tục vô tận.

Một số lớn hơn 1 mà không phải là số nguyên tố được gọi là số hợp số, bởi vì nó có thể được cấu tạo từ các ước số nhỏ hơn. Số 9 là số hợp số vì nó chia hết cho 3, và 15 là số hợp số vì nó chia hết cho cả 3 và 5.

Lưu ý: 0 và 1 không phải là số nguyên tố. 2 là số nguyên tố chẵn duy nhất, và các giá trị âm không bao giờ được coi là số nguyên tố.

Cách kiểm tra xem một số có phải là số nguyên tố hay không Java

Chiến lược kiểm tra là một phép thử chia hết đơn giản. Lấy giá trị cần kiểm tra, lần lượt chia cho từng số nguyên nhỏ hơn, và kiểm tra phần dư trả về bởi toán tử modulo. Phần dư bằng 0 chứng tỏ tồn tại một ước số, điều này ngay lập tức loại bỏ số đó.

Logic chương trình:

• Chúng ta cần chia một số đầu vào, ví dụ 17, cho các giá trị từ 2 đến 17 và kiểm tra số dư. Nếu số dư bằng 0, số đó không phải là số nguyên tố.
• Không có số nào chia hết cho hơn một nửa chính nó. Vì vậy chúng ta cần phải vòng lặp thông qua chỉ numberToCheck/2Nếu giá trị nhập vào là 17, một nửa là 8.5 và vòng lặp sẽ lặp qua các giá trị từ 2 đến 8.
• Nếu số cần kiểm tra chia hết cho một số khác, cờ isPrime sẽ được đặt thành true. false và vòng lặp được thoát ra.

Hai Java Các tính năng mang toàn bộ thuật toán. Toán tử modulo % trả về phần dư của phép chia số nguyên, và break Câu lệnh này dừng vòng lặp ngay khi biết được đáp án, do đó không có vòng lặp không cần thiết nào được thực hiện.

Java Chương trình kiểm tra xem một số có phải là số nguyên tố hay không.

Chương trình dưới đây gán giá trị 17 cho biến numberToCheck và in ra từng bước phép chia, để bạn có thể theo dõi từng dòng suy luận. Mã này có thể chỉnh sửa được, vì vậy hãy thay đổi giá trị và chạy lại với một số hợp số như 21 để xem kết quả ngược lại.

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");
    }
  }

Đầu ra mong đợi:

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

Vòng lặp dừng lại ở số 8 vì 17 chia cho 2 bằng 8 trong phép toán số nguyên. Vì số dư không bao giờ bằng 0, nên biến isPrime giữ nguyên giá trị ban đầu là true và điều kiện cuối cùng in ra kết quả tích cực.

Phương pháp kiểm tra số nguyên tố tối ưu bằng cách sử dụng phương pháp căn bậc hai

Chia đến một nửa số là đúng nhưng lãng phí. Nếu một số n có ước số lớn hơn căn bậc hai của nó, thì ước số tương ứng phải nhỏ hơn căn bậc hai, vì vậy nó đã được tìm thấy rồi. Do đó, kiểm tra đến √n sẽ cho cùng một kết quả với số lần lặp ít hơn nhiều.

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));
        }
    }
}

Đầu ra:

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

Điều kiện i * i <= n Phương pháp này tránh việc gọi hàm Math.sqrt cho số thực, và bước nhảy là 2 sẽ bỏ qua mọi ước số chẵn. Với một giá trị như 1,000,003, vòng lặp cơ bản thực hiện khoảng 500,000 lần lặp, trong khi phiên bản này thực hiện ít hơn 500 lần.

Kiểm tra số nguyên tố do người dùng nhập

Việc nhập dữ liệu trực tiếp rất tiện lợi cho việc minh họa, nhưng các bài tập thực tế thường yêu cầu nhập liệu từ bàn phím. Lớp Scanner đọc một số nguyên từ bảng điều khiển và truyền nó cho cùng phương thức isPrime.

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();
    }
}

Ví dụ chạy thử:

Enter a number: 29
29 is a Prime number

Những lỗi thường gặp khi viết chương trình về số nguyên tố

Hầu hết các lỗi khi nộp bài đều xuất hiện ở các giá trị biên chứ không phải ở vòng lặp chính. Danh sách dưới đây liệt kê các lỗi thường gặp nhất trong mã của người mới bắt đầu.

1. Bắt đầu vòng lặp từ 1: Mọi số nguyên đều chia hết cho 1, vì vậy cờ được đặt thành false ngay lập tức và chương trình báo cáo rằng không có số nào là số nguyên tố.
2. Coi 1 là số nguyên tố: Giá trị 1 chỉ có một ước số, vì vậy nó không thỏa mãn định nghĩa ước số hai và phải trả về false.
3. Bỏ qua câu lệnh break: Chương trình vẫn trả về câu trả lời đúng, nhưng nó tiếp tục lặp lại sau khi đã biết kết quả, điều này gây lãng phí thời gian đối với các dữ liệu đầu vào lớn.
4. Sử dụng i <= n như giới hạn: Con số này luôn tự chia hết cho chính nó, vì vậy vòng lặp phải dừng lại trước khi đạt đến n.
5. So sánh với = thay vì ==: Dấu bằng đơn lẻ gán giá trị thay vì kiểm tra giá trị đó, điều này dẫn đến lỗi biên dịch trong điều kiện if.

So sánh các phương pháp kiểm tra số nguyên tố

Hãy chọn phương pháp phù hợp với kích thước của dữ liệu đầu vào và việc cần kiểm tra một giá trị hay toàn bộ phạm vi giá trị.

Khi cần phân loại toàn bộ một phạm vi giá trị thay vì chỉ một giá trị đơn lẻ, phương pháp sàng lọc sẽ hiệu quả hơn nhiều. Chương trình hỗ trợ của chúng tôi để tìm kiếm... Thủ tướng Chính phủ Numbers từ 1 để 100 minh họa cho mô hình đó. Để biết thêm các bài tập liên quan đến vòng lặp, hãy xem lại phần... Dãy Fibonacci trong Java, Các Java chương trình đối xứng, và Bubble Thuật toán sắp xếp trong JavaNhững người mới chơi cần ôn lại cách tuyên bố cờ và phản công nên đọc thêm về... Java biến trong chính Java hướng dẫn.

Câu Hỏi Thường Gặp