质数筛的程序

import java.util.Arrays; import java.util.ArrayList; import java.util.List; public class PrimeSieve { /** * 返回 [2, n] 范围内所有质数的列表 */ public static List<Integer> sieveOfEratosthenes(int n) { if (n < 2) { return new ArrayList<>(); } // isPrime[i] 表示数字 i 是否为质数 boolean[] isPrime = new boolean[n + 1]; Arrays.fill(isPrime, true); // 0 和 1 不是质数 isPrime[0] = false; isPrime[1] = false; // 埃氏筛核心 for (int i = 2; i * i <= n; i++) { if (isPrime[i]) { // 从 i*i 开始标记，因为更小的倍数已被之前的质数标记过 for (int j = i * i; j <= n; j += i) { isPrime[j] = false; } } } // 收集结果 List<Integer> primes = new ArrayList<>(); for (int i = 2; i <= n; i++) { if (isPrime[i]) { primes.add(i); } } return primes; } // 打印前 30 个质数（演示用） public static void main(String[] args) { int limit = 100; List<Integer> primes = sieveOfEratosthenes(limit); System.out.println(limit + " 以内的质数共 " + primes.size() + " 个："); System.out.println(primes); } }