Java Chương trình in ấn Prime Numbers từ 1 để 100

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

A Số nguyên tố Số nguyên tố là số chỉ chia hết cho 1 hoặc chính nó. Nó là một số tự nhiên lớn hơn 1 mà không phải là tích của hai số tự nhiên nhỏ hơ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.v.

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

Giữa 1 và 100 có chính xác 25 số nguyên tố. Bảng dưới đây nhóm chúng theo từng thập kỷ, giúp làm nổi bật quy luật thưa thớt khi giá trị tăng lên.

Cách in Prime Numbers Từ 1 đến 100 Chương trình trong Java

Dưới đây là Java chương trình in ra các số nguyên tố từ 1 đến 100:

Logic chương trình:

• Phương pháp chính của chương trình số nguyên tố trong Java Chứa một vòng lặp để kiểm tra từng số nguyên tố từ 1 đến 100 một cách tuần tự.
• Phương thức chính gọi phương thức CheckPrime để xác định xem một số có phải là số nguyên tố hay không. Java hay không.
• 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 quá một nửa của chính nó. Vì vậy, chúng ta chỉ cần lặp qua giá trị của số cần kiểm tra là numberToCheck/2. Nếu số 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.
• If numberToCheck Nếu số đó hoàn toàn chia hết cho một số khác, ta trả về false và vòng lặp kết thúc.
• If numberToCheck là số nguyên tố, chúng ta trả về giá trị đúng.
• Trong phương pháp chính cho các số nguyên tố từ 1 đến 100 trong Java, kiểm tra xem isPrime có phải là TRUE và cộng giá trị đó vào số nguyên tốNumbersĐã tìm thấy chuỗi.
• Cuối cùng, in các số nguyên tố từ 1 đến 100 trong Java.

Việc tách riêng phương thức kiểm tra giúp chương trình có thể tái sử dụng. Phương thức CheckPrime tương tự có thể được gọi với bất kỳ giới hạn trên nào chỉ bằng cách thay đổi biến maxCheck.

public class PrimeNumbers {

    public static void main(String[] args) {

        int i;
        int num = 0;
        int maxCheck = 100; // maxCheck limit till which you want to find prime numbers
        boolean isPrime = true;

        //Empty String
        String primeNumbersFound = "";

        //Start loop 2 to maxCheck
        for (i = 2; i <= maxCheck; i++) {
            isPrime = CheckPrime(i);
            if (isPrime) {
                primeNumbersFound = primeNumbersFound + i + " ";
            }
        }
        System.out.println("Prime numbers from 1 to " + maxCheck + " are:");
        // Print prime numbers from 1 to maxCheck
        System.out.println(primeNumbersFound);
    }
    public static boolean CheckPrime(int numberToCheck) {
        int remainder;
        for (int i = 2; i <= numberToCheck / 2; i++) {
            remainder = numberToCheck % i;
            //if remainder is 0 then the number is not prime and we break the loop. Else continue the loop
            if (remainder == 0) {
                return false;
            }
        }
        return true;

    }

}

Đầu ra mong đợi:

Kết quả của số nguyên tố từ 1 đến 100 trong Java chương trình sẽ là:

Prime numbers from 1 to 100 are:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

Giá trị 2 được chấp nhận vì điều kiện vòng lặp bên trong i <= 2 / 2 đánh giá 2 <= 1Điều này ngay lập tức là sai, vì vậy phương thức trả về true mà không cần phép chia nào.

Phiên bản tối ưu hóa sử dụng giới hạn căn bậc hai

Chia đến một nửa số là đúng nhưng thực hiện công việc không cần thiết. Các ước số luôn xuất hiện theo cặp xung quanh căn bậc hai, vì vậy bất kỳ thừa số nào lớn hơn √n đều có một thừa số tương ứng nhỏ hơn nó đã được kiểm tra trước đó.

public class PrimeNumbersOptimized {

    public static void main(String[] args) {
        int maxCheck = 100;
        int count = 0;
        StringBuilder result = new StringBuilder();

        for (int i = 2; i <= maxCheck; i++) {
            if (isPrime(i)) {
                result.append(i).append(" ");
                count++;
            }
        }

        System.out.println("Prime numbers from 1 to " + maxCheck + " are:");
        System.out.println(result.toString().trim());
        System.out.println("Total primes found: " + count);
    }

    public static boolean isPrime(int n) {
        if (n <= 1) return false;
        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;
    }
}

Đầu ra:

Prime numbers from 1 to 100 are:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
Total primes found: 25

In ấn Prime Numbers Sử dụng sàng Eratosthenes

Khi cần tìm tất cả các số nguyên tố trong một dãy, phép chia thử không phải là công cụ phù hợp. Phương pháp sàng Eratosthenes xây dựng một mảng boolean, đánh dấu các bội số của mỗi số nguyên tố là hợp số, và đọc ra những số còn lại chưa được đánh dấu.

Phương pháp này hoạt động theo ba bước:

1. Tạo một mảng boolean có kích thước n+1 và giả sử mọi chỉ số từ 2 trở lên đều là số nguyên tố.
2. Bắt đầu từ số 2, đánh dấu mọi bội số của số nguyên tố hiện tại là hợp số.
3. Chuyển sang chỉ số chưa được đánh dấu tiếp theo và lặp lại cho đến khi vượt qua căn bậc hai của n.

import java.util.Arrays;

public class SieveOfEratosthenes {

    public static void main(String[] args) {
        int n = 100;
        boolean[] composite = new boolean[n + 1];

        for (int p = 2; p * p <= n; p++) {
            if (!composite[p]) {
                // start at p*p because smaller multiples are already marked
                for (int multiple = p * p; multiple <= n; multiple += p) {
                    composite[multiple] = true;
                }
            }
        }

        StringBuilder result = new StringBuilder();
        for (int i = 2; i <= n; i++) {
            if (!composite[i]) {
                result.append(i).append(" ");
            }
        }

        System.out.println("Prime numbers from 1 to " + n + " are:");
        System.out.println(result.toString().trim());
    }
}

Đầu ra:

Prime numbers from 1 to 100 are:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

So sánh ba phương pháp

Cả ba chương trình đều in ra cùng 25 giá trị, vì vậy sự lựa chọn hoàn toàn phụ thuộc vào kích thước của phạm vi.

Hãy xem chương trình của chúng tôi để tìm hiểu thêm. số nguyên tố từ bất kỳ số đầu vào nào Khi cần kiểm tra một giá trị duy nhất thay vì một phạm vi giá trị. Để thực hiện thêm các bài tập về 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 JavaMảng boolean được sử dụng bởi thuật toán sàng sẽ được giải thích chi tiết hơn ở phần sau. Java mảng.

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