Java 打印 Prime 的程序 Numbers 从1到100

什么是质数？

A 素数 质数是指只能被1或它本身整除的数。它是大于1的自然数，且不是两个较小自然数的乘积。例如，11只能被1或它本身整除。其他质数还有2、3、5、7、11、13、17等等。

注意： 0 和 1 不是质数。2 是唯一的偶质数。

1到100之间恰好有25个质数。下面的表格按十位数对它们进行分组，这样就可以清楚地看到随着数值增大，质数逐渐减少的规律。

如何打印 Prime Numbers 1 至 100 之间的程序 Java

下面是 Java 打印从 1 到 100 的素数的程序：

程序逻辑：

• 主要方法是 素数程序 Java 包含一个循环，用于逐个检查 1 到 100 之间的质数。
• main方法调用该方法 CheckPrime 判断一个数是否为质数 Java 或没有。
• 我们需要将一个输入的数字（例如 17）分别除以 2 到 17 之间的任意值，并检查余数。如果余数为 0，则该数字不是质数。
• 任何数字都不能被它自身的一半以上整除。因此，我们只需要循环遍历 numberToCheck/2。如果输入是 17，那么它的一半是 8.5，循环将遍历 2 到 8 之间的值。
• If numberToCheck 如果一个数能被另一个数整除，则返回 false，循环结束。
• If numberToCheck 为素数，则返回 true。
• 在主方法中，对于 1 到 100 的素数 Java检查 isPrime 是否为 TRUE 并将该值加到质数上Numbers找到字符串。
• 最后，打印 1 到 100 之间的素数 Java.

将检查功能分离成一个单独的方法，使得程序可以重用。只需更改 maxCheck 变量，就可以使用相同的 CheckPrime 方法并设置任意上限值。

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;

    }

}

预期产量：

输出 1 到 100 之间的质数 Java 程序 将会：

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

值 2 通过，因为内循环条件成立。 i <= 2 / 2 评估为 2 <= 1结果立即为假，因此该方法无需任何除法运算即可返回 true。

使用平方根界限的优化版本

将数除以二是正确的，但这会造成不必要的计算。除数总是成对出现在根号附近，因此任何大于√n的因数在其下方都有一个已经计算过的对应因数。

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

输出：

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

打印主线 Numbers 使用埃拉托色尼筛法

当需要计算某个范围内的所有质数时，试除法并不适用。埃拉托色尼筛法构建一个布尔数组，将每个质数的倍数标记为合数，然后读取剩余的未标记数。

该方法分三步进行：

1. 创建一个大小为 n+1 的布尔数组，并假设从 2 开始的每个索引都是质数。
2. 从 2 开始，将当前素数的每个倍数标记为合数。
3. 前进到下一个未标记的索引，重复此操作，直到超过 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());
    }
}

输出：

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

三种方法的比较

这三个程序都打印相同的 25 个值，因此选择完全取决于范围的大小。

查看我们的程序以了解更多信息 从任意输入数字中求质数 当需要测试单个值而不是一个范围时。有关更多循环驱动的练习，请参阅…… 斐波那契数列 Java， Java 回文程序，并 Bubbl排序算法 Java筛法使用的布尔数组将在下文中进一步解释。 Java 数组.

常见问题