正文

java计算1到100之间所有素数的方法

/0 浏览量
0412

在Java中，计算1到100之间的所有素数是一个常见的编程练习。素数是指只能被1和它本身整除的大于1的自然数。以下是一种计算1到100之间所有素数的方法。

方法一：基本的遍历检查

这个方法涉及到遍历1到100的每一个数字，并对每个数字检查它是否是素数。

public class PrimeNumbers {
    public static void main(String[] args) {
        int maxLimit = 100;

        for (int num = 2; num <= maxLimit; num++) {
            if (isPrime(num)) {
                System.out.println(num);
            }
        }
    }

    private static boolean isPrime(int number) {
        if (number <= 1) {
            return false;
        }
        for (int i = 2; i <= Math.sqrt(number); i++) {
            if (number % i == 0) {
                return false;
            }
        }
        return true;
    }
}

解释：

  1. main 方法设置了一个上限值 maxLimit，即我们想要检查的数字范围。
  2. 我们使用一个for循环来遍历从2到 maxLimit 的每一个数字。
  3. isPrime 方法用于检查一个数字是否是素数。如果数字小于等于1，它就不是素数。否则，我们遍历从2到 number 的平方根的所有数字，如果找到一个可以整除 number 的数字，那么它就不是素数。
  4. 如果 isPrime 方法返回 true，我们就打印出该数字。

方法二：埃拉托斯特尼筛法（Sieve of Eratosthenes）

埃拉托斯特尼筛法是一种更高效的方法来找出一定范围内所有的素数。以下是如何在Java中使用这种方法来找出1到100之间的所有素数。

public class SieveOfEratosthenes {
    public static void main(String[] args) {
        int maxLimit = 100;
        boolean[] prime = new boolean[maxLimit + 1];

        for (int i = 2; i <= maxLimit; i++) {
            prime[i] = true;
        }

        for (int p = 2; p * p <= maxLimit; p++) {
            if (prime[p]) {
                for (int i = p * p; i <= maxLimit; i += p) {
                    prime[i] = false;
                }
            }
        }

        for (int i = 2; i <= maxLimit; i++) {
            if (prime[i]) {
                System.out.println(i);
            }
        }
    }
}

解释：

  1. 我们首先创建了一个布尔数组 prime，用于标记每个数字是否是素数。默认情况下，所有数字都被认为是素数（除了0和1）。
  2. 然后，我们从2开始遍历到 maxLimit 的平方根，并使用嵌套的循环来标记每个素数的倍数不是素数。
  3. 最后，我们再次遍历 prime 数组，打印出所有标记为 true 的数字，即素数。

这两种方法都是找出1到100之间所有素数的有效方法。第一种方法较为直观，但效率较低。第二种方法，埃拉托斯特尼筛法，则更加高效，特别是对于大范围的素数搜索。

-- 展开阅读全文 --