Java实现求小于n的质数的3种方法

在编程领域，特别是Java语言中，寻找小于特定数值n的所有质数是一项常见的任务。质数是数学中的一个重要概念，它是指大于1且只有1和它自身两个正因数的自然数。在这里，我们将探讨三种不同的Java实现方法来找出小于n的所有质数。 1. **根据定义求解**： 这种方法是最直观的，但效率较低。代码中，我们遍历从2到n-1的每个整数i，然后再次内循环检查是否有其他数可以整除i。如果i能被2到i-1之间的任意数整除，那么它就不是质数。如果有且仅有一个数（即i自身）能整除i，那么i就是质数。这种方法的时间复杂度较高，约为O(n^2)。 2. **利用平方根优化**： 这个方法是基于一个数学性质：如果一个数n不是质数，那么它至少有一个因子小于或等于其平方根。因此，我们只需要检查到sqrt(n)即可，无需遍历到n-1。这大大提高了效率，时间复杂度降低到O(n*sqrt(n))。代码中，我们创建了一个名为m的方法，用于判断一个数是否为质数，通过只检查到num的平方根，显著减少了计算量。 3. **找规律**： 虽然这种方法没有明确的代码展示，但从描述中我们可以推断，它可能利用了质数的一些特性。比如，最小的质数是2，也是唯一的偶数质数，其他质数都是奇数。此外，质数在数轴上分布有一定的规律，例如著名的埃拉托斯特尼筛法。这种方法可能会通过筛选掉所有的偶数（除了2），然后逐个检查剩余的奇数是否为质数，进一步优化搜索过程。 在上述的代码示例中，`divisible`方法是用于判断一个数n是否能被已知的质数列表中的任何数整除，这在埃拉托斯特尼筛法中会用到。埃拉托斯特尼筛法是一种有效的找出所有小于n的质数的方法，它通过依次排除每个质数的倍数，从而找出所有的质数。 总结来说，这三种方法分别代表了从基础到优化的求质数策略。初级方法直接应用质数定义，适合理解基本概念；平方根优化法是中级策略，适用于大多数情况；而找规律则更倾向于高级算法，通常结合特定的数论知识来提高效率。在实际开发中，我们应根据性能需求和问题规模选择合适的方法。