java如何判断一个数是否是素数(质数)

判断一个数是否是素数是一个常见的算法问题，下面是用java编写的实现方法：

1.判断算法

判断一个数x是否为素数的方法是判断x是否能被2~sqrt(x)范围内的整数整除。如果有一个数能够整除x，那么x就不是素数，否则x就是素数。

示例代码：

public static boolean isPrime(int x) {
    if (x < 2) {  // 小于2的数都不是素数
        return false;
    }
    for (int i = 2; i <= Math.sqrt(x); i++) {
        if (x % i == 0) {   // 能够整除
            return false;
        }
    }
    return true;
}

2.测试算法

为了测试isPrime算法的正确性，我们可以编写一个程序，用于判断指定范围内的所有整数是否为素数，并输出结果。

示例代码：

public static void main(String[] args) {
    int n = 100;
    System.out.printf("2~%d的素数：\n", n);
    for (int i = 2; i <= n; i++) {
        if (isPrime(i)) {
            System.out.print(i + " ");
        }
    }
}

输出结果：

2~100的素数：
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~100的素数，结果与数学事实相符。因此可以证明isPrime算法的正确性。

3.优化算法

在调用isPrime算法时，我们只需要判断2~sqrt(x)范围内是否有数能够整除x，因此可以做个小优化：只需判断2和所有奇数是否能够整除x即可，因为偶数都能够被2整除。

修改isPrime算法：

public static boolean isPrime(int x) {
    if (x < 2) {  // 小于2的数都不是素数
        return false;
    }
    if (x == 2 || x == 3) {  // 2和3都是素数
        return true;
    }
    if (x % 2 == 0) {  // 偶数都不是素数
        return false;
    }
    for (int i = 3; i <= Math.sqrt(x); i += 2) {
        if (x % i == 0) {   // 能够整除
            return false;
        }
    }
    return true;
}

这个修改后的算法将只会判断2和所有奇数是否能够整除x，从而加快了算法的执行速度。

示例代码：

public static void main(String[] args) {
    int n = 100;
    System.out.printf("2~%d的素数：\n", n);
    for (int i = 2; i <= n; i++) {
        if (isPrime(i)) {
            System.out.print(i + " ");
        }
    }
}

输出结果：

2~100的素数：
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 

可以看到，输出结果与前面的测试结果相同，但是这个算法的执行速度要更快。