SievePrimeNumbersJava实现埃拉托斯特尼筛法找质数

筛法求质数在计算机科学中，求解质数是基础算法之一，而“筛法”是最常用的求解质数的方法。这里的筛号即是指筛法求质数，具体指的是“埃拉托斯特尼筛法”。埃拉托斯特尼筛法是一种有效的找出所有小于给定数的质数的算法，由古希腊数学家埃拉托斯特尼提出。该方法通过逐步排除非质数（合数）来找到质数。

Java 实现在Java编程语言中，我们可以使用埃拉托斯特尼筛法来编写一个程序，该程序可以打印出所有小于用户指定数字的质数。我们需要创建一个足够大的数组，用于标记每个数是否为质数。初始时，数组中的所有元素都被视为质数。然后，我们从2开始，将所有2的倍数标记为非质数，接着是3的所有倍数，直到根号下给定的数字。这样，未被标记的数字就是质数。

以下是一个简单的Java程序实现：

import java.util.Scanner;



public class SieveOfEratosthenes {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        System.out.println(\"请输入一个整数：\");

        int n = scanner.nextInt();



        boolean[] primes = new boolean[n + 1];

        for (int i = 2; i * i <= n; i++) {

            if (!primes[i]) {

                for (int j = i * i; j <= n; j += i) {

                    primes[j] = true;

                }

            }

        }



        System.out.println(\"小于或等于\" + n + \"的质数有：\");

        for (int i = 2; i <= n; i++) {

            if (!primes[i]) {

                System.out.print(i + \" \");

            }

        }

    }

}

在这个程序中，我们首先从用户那里获取一个整数n，然后创建一个布尔数组primes，长度为n+1。接着，我们遍历从2到根号下n的所有数字，如果某个数字没有被标记为非质数（!primes[i]），那么它的所有倍数都将被标记为非质数。我们打印出所有未被标记的数字，即为质数。