正文

掌握Java编写质数的方法，轻松判断数字是否为质数

/0 浏览量
0629

在数学领域，质数是那些只能被1和它本身整除的自然数，且大于1。例如，2、3、5、7、11等都是质数。在编程中，判断一个数字是否为质数是一个基础且常见的任务。下面，我将详细介绍在Java中编写质数判断方法的几种常用方法。

1. 基础方法：试除法

最简单的方法是使用试除法。这种方法从2开始，一直除到这个数的平方根。如果在这个范围内没有能整除它的数，那么这个数就是质数。

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

    public static void main(String[] args) {
        int number = 29;
        if (isPrime(number)) {
            System.out.println(number + " 是质数。");
        } else {
            System.out.println(number + " 不是质数。");
        }
    }
}

2. 优化方法：埃拉托斯特尼筛法

埃拉托斯特尼筛法是一种更高效的方法，它通过筛选掉所有小于或等于给定数的质数来找出所有质数。这种方法在处理大量数字时特别有用。

public class SieveOfEratosthenes {
    public static void printPrimes(int n) {
        boolean[] isPrime = new boolean[n + 1];
        for (int i = 2; i <= n; i++) {
            isPrime[i] = true;
        }
        for (int factor = 2; factor * factor <= n; factor++) {
            if (isPrime[factor]) {
                for (int j = factor * factor; j <= n; j += factor) {
                    isPrime[j] = false;
                }
            }
        }
        for (int i = 2; i <= n; i++) {
            if (isPrime[i]) {
                System.out.print(i + " ");
            }
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int n = 30;
        printPrimes(n);
    }
}

3. 高效方法：概率算法

对于非常大的数字，使用传统的试除法可能会非常慢。在这种情况下，可以使用概率算法，如Miller-Rabin素性测试。这种方法基于概率，不是绝对判断一个数是否为质数，但可以以很高的概率确定。

import java.math.BigInteger;
import java.util.Random;

public class MillerRabinTest {
    private static final Random random = new Random();

    public static boolean isPrime(BigInteger number, int certainty) {
        if (number.compareTo(BigInteger.TWO) < 0) {
            return false;
        }
        if (number.compareTo(BigInteger.TWO) == 0 || number.compareTo(BigInteger.valueOf(3)) == 0) {
            return true;
        }
        if (number.mod(BigInteger.TWO).equals(BigInteger.ZERO)) {
            return false;
        }
        BigInteger d = number.subtract(BigInteger.ONE);
        while (d.mod(BigInteger.TWO).equals(BigInteger.ZERO)) {
            d = d.divide(BigInteger.TWO);
        }
        for (int i = 0; i < certainty; i++) {
            BigInteger a = new BigInteger(number.bitLength(), random);
            BigInteger x = a.modPow(d, number);
            if (x.equals(BigInteger.ONE) || x.equals(number.subtract(BigInteger.ONE))) {
                continue;
            }
            boolean isComposite = true;
            while (d.compareTo(BigInteger.ONE) > 0) {
                x = x.modPow(BigInteger.TWO, number);
                if (x.equals(BigInteger.ONE)) {
                    return false;
                }
                if (x.equals(number.subtract(BigInteger.ONE))) {
                    isComposite = false;
                    break;
                }
            }
            if (isComposite) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        BigInteger number = new BigInteger("104729");
        int certainty = 5;
        if (isPrime(number, certainty)) {
            System.out.println(number + " 是质数。");
        } else {
            System.out.println(number + " 不是质数。");
        }
    }
}

通过上述方法，你可以在Java中轻松地判断一个数字是否为质数。选择哪种方法取决于你的具体需求，如数字的大小和计算效率。希望这些方法能帮助你更好地理解质数的概念和Java编程。

-- 展开阅读全文 --