LeetCode统计小于n的素数题Java代码提交仅过4/66用例排查

本地运行代码可得到预期输出，但在LeetCode平台提交无法通过，对应题目为统计小于整数n的素数个数，题目约束范围为0 <= n <= 5 * 10^6，提交后仅通过66个测试用例中的4个。

class Solution {
    
    public static int count = 1;
    
    public int countPrimes(int n) {
        
        if (n == 0 || n == 1 || n == 2)
            return 0;
        else
            for (int i = 3; i < n; i++) {
                
                for (int j = 2; j < i; j++) {
                    if (i % j == 0) {
                        break;
                    } else if (j == i - 1 && i % j != 0) {
                        count++;
                    }
                }
            }
        return count;
    }
}

• 核心错误：静态变量导致用例间状态污染
  你把计数变量count定义为类级别的静态变量，静态变量的生命周期和类一致，不会随方法调用结束重置。LeetCode判题时会复用同一个Solution类实例执行全部测试用例，上一个测试用例累加得到的count值会直接带入下一个用例的计算，导致结果完全错误。而你本地测试每次都是重新启动JVM运行，类会重新加载，静态变量每次都会恢复初始值1，所以本地测试看起来结果正常。
• 算法效率不满足数据规模要求
  你当前用的暴力枚举判断素数的逻辑时间复杂度为O(n²)，题目n的上限是5*10^6，这个复杂度下计算量会达到万亿级别，哪怕修复了静态变量的问题，也会因为运行超时无法通过用例。
• 边界逻辑耦合度高
  初始count固定写为1，本质是提前把素数2计入总数，这种硬编码的逻辑和遍历逻辑耦合，一旦输入边界变化很容易出现计算错误。

• 把计数变量count移到countPrimes方法内部定义，每次方法调用时重新初始化，不要用静态变量存储和单次调用相关的状态。
• 替换暴力判断逻辑为埃拉托斯特尼筛法（埃氏筛），通过标记合数的方式统计素数，时间复杂度可以降到O(n log log n)，能够轻松支撑5*10^6的数据规模。

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