C++埃拉托斯特筛子求质数算法

### 计算素数的Java实现 在Java中，可以通过多种方式来计算素数。以下是基于提供的引用以及常见算法的一种高效实现方案。 #### 方法概述 为了判断一个数是否为素数，可以采用以下逻辑： - 如果数字小于2，则它不是素数。 - 对于大于等于2的数字，检查是否存在从2到该数平方根范围内的因子。如果没有发现任何因子能够整除此数，则它是素数。 这种方法的时间复杂度接近O(√n)，相较于逐一检查所有较小数值更为优化[^2]。 #### 完整代码示例 下面是一个完整的Java程序，用于找出指定范围内所有的素数： ```java public class PrimeNumbers { public static void main(String[] args) { int upperBound = 100; // 可调整上限值 System.out.println("素数列表:"); for (int i = 2; i <= upperBound; i++) { if (isPrime(i)) { // 调用辅助函数检测当前数字是否为素数 System.out.print(i + " "); } } } private static boolean isPrime(int num) { if (num < 2) return false; // 遍历至sqrt(num), 提升效率 for (int j = 2; j * j <= num; j++) { if (num % j == 0) return false; // 存在一个因子可整除num, 则非素数 } return true; // 若无任何因子满足条件, 返回true表明其为素数 } } ``` 上述代码定义了一个`main`方法用来设置查找区间，并调用了名为`isPrime`的帮助函数逐个验证候选者是否符合条件。注意这里只迭代到了可能因子的最大界限即`sqrt(num)`处以减少不必要的运算次数^。 另外一种思路则是利用埃拉托斯特尼筛法(Sieve of Eratosthenes)，这是一种更高效的批量筛选素数的技术，在处理较大规模数据集时表现尤佳[^3]。 #### 埃氏筛法版本 下面是另一种基于埃拉托色尼斯筛选原理的解决方案: ```java import java.util.Arrays; public class SieveOfEratosthenes { public static void main(String[] args){ final int MAX=50;//设定最大边界 boolean [] primes=new boolean[MAX+1]; Arrays.fill(primes,true); primes[0]=primes[1]=false; for(int p=2;p*p<=MAX;p++){ if(primes[p]){ for(int multiple=p*p;multiple<=MAX;multiple+=p){ primes[multiple]=false; } } } System.out.println("Primes up to "+MAX+":"); for(int k=0;k<primes.length;k++) if(primes[k])System.out.print(k+" "); } } ``` 在此版实现里，我们先初始化一个布尔型数组标记每一位初始状态均为潜在素数(true)，随后逐步淘汰掉各已知最小质因数倍率位置上的成员直至整个序列扫描完毕为止[^4].