sdut-判断素数JAVA

### 如何用Java编写判断素数的程序 在Java中，可以通过多种方式实现素数判断的功能。下面提供一种常见的方法来检测给定整数是否为素数。 #### 方法一：简单循环检查法 这种方法通过遍历从`2`至目标数值平方根之间的所有整数，逐一尝试作为除数去除目标值，以此判定该数是否能被任何小于自身的数整除。如果存在可以整除的情况，则说明此数不是素数；反之则是素数[^4]。 ```java public class PrimeChecker { public static boolean isPrime(int num) { if (num <= 1) return false; for (int i = 2; i * i <= num; ++i) { // 只需测试到sqrt(num)，因为因子总是成对出现 if (num % i == 0) return false; } return true; } public static void main(String[] args) { int testNumber = 17; System.out.println(testNumber + " 是素数吗？" + isPrime(testNumber)); } } ``` 上述代码定义了一个名为 `isPrime()` 的静态函数，接受一个整型参数并返回布尔类型的真伪值表示输入数字是否为素数。主函数部分调用了这个辅助函数来进行具体某个数（此处设定了变量 `testNumber` 来存储待测数据）的素性检验，并打印出结果。 为了提高效率，在实际应用中通常只需要考虑直到√n范围内的可能因子即可完成有效的筛选过程[^5]。 #### 方法二：埃拉托斯特尼筛法优化版 对于更大规模的数据集或者频繁查询场景下，还可以采用更高效的算法——埃氏筛法及其改进版本。这里给出一段基于位运算的空间节省型实现： ```java import java.util.Arrays; public class SieveOfEratosthenes { private final byte[] sieve; /** * 构造器初始化指定大小的最大边界内所有的素数状态表. */ public SieveOfEratosthenes(int maxLimit) { this.sieve = new byte[(maxLimit >> 3) + 1]; Arrays.fill(this.sieve, (byte) 0xFF); // 初始化全置为1(即假设全部都是素数) setBit(0); setBit(1); for (long n = 2L; n * n < maxLimit;) { long m = nextClearBit(n); while ((m *= m) < maxLimit && !getBit(m)) { setBit((int)m); m += n; } n++; } } /** * 设置特定位置上的标志位为已占用/非素数. * * @param index 要设置的位置索引 */ private void setBit(long index) { if (index >= 0) { int byteIndex = (int)(index >>> 3); int bitMask = ~(1 << (index & 7)); sieve[byteIndex] &= bitMask; } } /** * 获取下一个未被标记过的最小合数对应的起始点. * * @param start 开始寻找的地方 * @return 下一个可用作新轮次起点的合数值 */ private long nextClearBit(long start) { do { int bytePos = (int)(start >>> 3); if (((sieve[bytePos]) | ~(-1)) != 0) { int bitOffset = Integer.numberOfTrailingZeros(~sieve[bytePos]); return ((bytePos << 3) | bitOffset); } else { start |= 7L; start++; } } while (++start > 0); throw new AssertionError(); } /** * 判断某一位是否已经被标记过. * * @param pos 需要检查的状态位编号 * @return 如果对应位已被清除则返回false，否则返回true */ private boolean getBit(int pos) { return (pos >= 0) && ((this.sieve[pos >>> 3] & (1 << (pos & 7))) != 0); } /** * 测试接口供外部调用以确认单个整数是不是素数. * * @param value 待查证的目标整数 * @return 若value确实属于素数范畴就回传True，反之False */ public boolean contains(int value) { return getBit(value); } public static void main(String[] args) { SieveOfEratosthenes soe = new SieveOfEratosthenes(1000000); System.out.printf("%d 是否是素数：%b%n", 9973, soe.contains(9973)); } } ``` 这段更为复杂的例子展示了如何利用预先计算好的大范围内所有素数的信息快速响应任意询问。虽然初次构建成本较高，但对于多次重复访问同一区间的情形特别有用。