java质数如何

判断质数的基本方法

质数是指大于1的自然数，且只能被1和它本身整除的数。在Java中，可以通过以下方法判断一个数是否为质数。

方法一：暴力检查法 从2开始遍历到n-1，检查n是否能被其中任何一个数整除。如果都不能，则n是质数。

public static boolean isPrime(int n) {
    if (n <= 1) {
        return false;
    }
    for (int i = 2; i < n; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

方法二：优化检查范围 实际上只需要检查到√n即可，因为如果n能被大于√n的数整除，那么它必定也能被小于√n的数整除。

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

生成质数列表

如果需要生成一定范围内的所有质数，可以使用埃拉托斯特尼筛法（Sieve of Eratosthenes）。

public static void sieveOfEratosthenes(int n) {
    boolean[] prime = new boolean[n + 1];
    Arrays.fill(prime, true);
    prime[0] = prime[1] = false;

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

    for (int i = 2; i <= n; i++) {
        if (prime[i]) {
            System.out.print(i + " ");
        }
    }
}

性能优化

对于大数判断质数，可以进一步优化：

• 跳过偶数检查（除了2）。
• 使用Miller-Rabin等概率性算法。

public static boolean isPrimeOptimized(int n) {
    if (n <= 1) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;
    for (int i = 3; i <= Math.sqrt(n); i += 2) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

实际应用示例

以下是一个完整的Java程序，演示如何判断一个数是否为质数：

import java.util.Scanner;

public class PrimeNumberChecker {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter a number: ");
        int num = scanner.nextInt();

        if (isPrime(num)) {
            System.out.println(num + " is a prime number.");
        } else {
            System.out.println(num + " is not a prime number.");
        }
        scanner.close();
    }

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

通过以上方法，可以高效地判断质数或生成质数列表。