Java 中质数相关代码解析

简介

在数学领域，质数是指在大于 1 的自然数中，除了 1 和它自身外，不能被其他自然数整除的数。在编程中，判断一个数是否为质数是一个常见的基础算法问题。Java 作为一种广泛使用的编程语言，提供了多种方式来实现质数相关的代码。本文将深入探讨 Java 中质数代码的基础概念、使用方法、常见实践以及最佳实践，帮助读者更好地理解和运用这一知识。

质数的基础概念

质数具有以下特性： - 质数大于 1。 - 质数只有两个正因数，即 1 和它本身。例如，2、3、5、7、11 都是质数，因为它们只能被 1 和自身整除；而 4 不是质数，因为它可以被 1、2、4 整除。

Java 中判断质数的基本代码实现

简单暴力解法

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

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

在这段代码中： - isPrime 方法用于判断一个整数是否为质数。 - 首先检查数字是否小于等于 1，如果是，则直接返回 false，因为质数必须大于 1。 - 然后通过一个 for 循环，从 2 到 number - 1 检查是否有数字能整除 number，如果有，则返回 false。 - 如果循环结束没有找到能整除的数字，则返回 true。

优化的暴力解法

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

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

优化点说明： - 首先单独处理数字 2，因为 2 是唯一的偶质数。 - 如果数字是偶数且不是 2，则直接返回 false。 - 在 for 循环中，只需要检查到 sqrt(number) 即可，因为如果 number 有一个大于 sqrt(number) 的因数，那么必然有一个小于 sqrt(number) 的因数。 - 循环步长设为 2，因为除了 2 以外的偶数都不是质数，这样可以减少不必要的计算。

常见实践 - 生成质数列表

生成一定范围内的质数列表

import java.util.ArrayList;
import java.util.List;

public class PrimeListGenerator {
    public static List<Integer> generatePrimes(int limit) {
        List<Integer> primes = new ArrayList<>();
        for (int number = 2; number <= limit; number++) {
            boolean isPrime = true;
            for (int i = 2; i * i <= number; i++) {
                if (number % i == 0) {
                    isPrime = false;
                    break;
                }
            }
            if (isPrime) {
                primes.add(number);
            }
        }
        return primes;
    }

    public static void main(String[] args) {
        int limit = 100;
        List<Integer> primes = generatePrimes(limit);
        System.out.println("小于等于 " + limit + " 的质数有:");
        for (int prime : primes) {
            System.out.print(prime + " ");
        }
    }
}

这段代码： - generatePrimes 方法用于生成小于等于指定 limit 的所有质数列表。 - 通过两层循环，外层循环遍历从 2 到 limit 的所有数字，内层循环检查每个数字是否为质数。 - 如果一个数字是质数，则将其添加到 primes 列表中。

优化与最佳实践

Sieve of Eratosthenes 算法

import java.util.ArrayList;
import java.util.List;

public class SieveOfEratosthenes {
    public static List<Integer> generatePrimes(int n) {
        boolean[] isPrime = new boolean[n + 1];
        for (int i = 2; i <= n; i++) {
            isPrime[i] = true;
        }
        for (int p = 2; p * p <= n; p++) {
            if (isPrime[p]) {
                for (int i = p * p; i <= n; i += p) {
                    isPrime[i] = false;
                }
            }
        }
        List<Integer> primes = new ArrayList<>();
        for (int i = 2; i <= n; i++) {
            if (isPrime[i]) {
                primes.add(i);
            }
        }
        return primes;
    }

    public static void main(String[] args) {
        int limit = 100;
        List<Integer> primes = generatePrimes(limit);
        System.out.println("小于等于 " + limit + " 的质数有:");
        for (int prime : primes) {
            System.out.print(prime + " ");
        }
    }
}

Sieve of Eratosthenes 算法原理： - 初始化一个布尔数组 isPrime，所有索引大于 1 的元素初始化为 true。 - 从 2 开始，将 2 的倍数都标记为非质数（即 false）。 - 接着处理下一个未被标记的数字（即质数），将其倍数都标记为非质数。 - 最后遍历数组，将所有标记为 true 的索引值添加到质数列表中。这种算法的时间复杂度为 O(n log log n)，相比之前的方法效率更高，特别是在生成较大范围内的质数时。

小结

本文详细介绍了 Java 中与质数相关的代码实现。从判断单个数字是否为质数的基本暴力解法，到优化的暴力解法，再到生成质数列表的常见实践，以及使用 Sieve of Eratosthenes 算法的最佳实践。不同的方法适用于不同的场景，读者可以根据实际需求选择合适的算法。掌握这些知识不仅有助于解决算法问题，还能提升对 Java 语言的运用能力。

参考资料

《Effective Java》 - Joshua Bloch
Oracle Java 官方文档
LeetCode、HackerRank 等算法练习平台上的质数相关题目