如何优化多测试用例下区间素数生成算法的性能？

嘿，我明白你现在的困扰——处理大区间素数生成时速度跟不上，尤其是当n达到1e9这种量级的时候，普通方法肯定会拉胯。你怀疑addPrimeNumbers方法有问题，这个方向是对的，大概率是你用了不适合大区间的素数筛选逻辑。

问题根源分析 #

首先，普通的埃氏筛法（生成从2到n的素数）在n=1e9时完全不可行，因为需要的内存会达到几十MB甚至几百MB，而且时间复杂度也顶不住。而试除法逐个判断每个数是否为素数，对于n-m=1e5的区间来说，每个数都试除到√x，时间成本也会很高，尤其是当x接近1e9时，√x是3e4，1e5次这样的操作就会慢下来。

最优解决方案：区间筛法（Segmented Sieve） #

针对你这种1≤m≤n≤1e9且n-m≤1e5的场景，区间筛法是完美适配的。核心思路是：

• 区间[m,n]里的合数，它的最小质因数一定不超过√n。所以我们先找出所有≤√n的素数。
• 用这些素数去标记区间[m,n]里的合数，剩下的未被标记的数就是区间内的素数。

具体实现步骤 #

1. 生成≤√n的所有素数：用普通的埃氏筛法就能搞定，因为√1e9=31622，这个量级的素数生成非常快。
2. 初始化区间标记数组：创建一个长度为n-m+1的布尔数组isPrimeInRange，初始值设为true（先假设所有数都是素数）。注意如果m=1，要把索引0对应的1标记为false（1不是素数）。
3. 标记区间内的合数：对于每个≤√n的素数p：
   • 找到区间[m,n]里第一个≥pp且是p的倍数的数，记为start。如果pp < m，那么start就是大于等于m的最小p的倍数（可以用((m + p - 1) / p) * p计算）。
   • 从start开始，每次加p，把对应的数组索引（start - m）标记为false。
4. 收集结果：遍历标记数组，所有isPrimeInRange[i]为true的位置，对应的数是m+i，这些就是区间内的素数。

优化后的Java代码示例 #

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

public class PrimeNumbers {
    public static List<Integer> getPrimesInRange(int m, int n) {
        List<Integer> result = new ArrayList<>();
        if (m < 2) m = 2; // 小于2的数没有素数
        
        // 步骤1：生成所有<=sqrt(n)的素数
        int sqrtN = (int) Math.sqrt(n);
        boolean[] isPrimeSmall = new boolean[sqrtN + 1];
        for (int i = 2; i <= sqrtN; i++) {
            isPrimeSmall[i] = true;
        }
        for (int i = 2; i * i <= sqrtN; i++) {
            if (isPrimeSmall[i]) {
                for (int j = i * i; j <= sqrtN; j += i) {
                    isPrimeSmall[j] = false;
                }
            }
        }
        List<Integer> smallPrimes = new ArrayList<>();
        for (int i = 2; i <= sqrtN; i++) {
            if (isPrimeSmall[i]) {
                smallPrimes.add(i);
            }
        }
        
        // 步骤2：初始化区间标记数组
        boolean[] isPrimeInRange = new boolean[n - m + 1];
        for (int i = 0; i < isPrimeInRange.length; i++) {
            isPrimeInRange[i] = true;
        }
        if (m == 1) {
            isPrimeInRange[0] = false; // 1不是素数
        }
        
        // 步骤3：用小素数标记区间内的合数
        for (int p : smallPrimes) {
            // 找到区间内第一个>=max(p*p, m)的p的倍数
            int start = Math.max(p * p, ((m + p - 1) / p) * p);
            for (int j = start; j <= n; j += p) {
                isPrimeInRange[j - m] = false;
            }
        }
        
        // 步骤4：收集素数
        for (int i = 0; i < isPrimeInRange.length; i++) {
            if (isPrimeInRange[i]) {
                result.add(m + i);
            }
        }
        return result;
    }

    // 测试方法
    public static void main(String[] args) {
        int t = 2; // 测试用例数
        int[][] testCases = {{10, 30}, {100000000 - 100000, 100000000}};
        for (int[] caseItem : testCases) {
            List<Integer> primes = getPrimesInRange(caseItem[0], caseItem[1]);
            System.out.println("区间[" + caseItem[0] + "," + caseItem[1] + "]的素数：");
            System.out.println(primes);
        }
    }
}

为什么这个方法更快？ #

• 生成小素数的时间可以忽略不计（√1e9才3万多）。
• 标记区间合数的操作只需要遍历每个小素数的倍数，总操作次数大约是(n-m)/2 + (n-m)/3 + ... + (n-m)/p，其中p是≤√n的最大素数，这个量级对于n-m=1e5来说完全可控，运行速度会比你之前的方法快很多。

如果你的addPrimeNumbers之前是用试除法或者全局筛法，换成这个区间筛法之后，性能会有质的提升。

内容的提问来源于stack exchange，提问作者jackfield