关于Java数组越界的一个诡异问题【leetcode204】

浏览数：47 / 时间：2015年06月08日

刷leetcode204时，质数计算，在看完改进算法后有个测试怎么也过不了，数据越界报错：

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -2146737495

仔细看都没有找到原因，其中最后两行输出为：

499813 499979 701 713
-2146737495 499979 46349 46349

很纳闷，怎么突然从701跳到了46349，而且i*j<n也是验证过的，这个疑惑只在CSDN上找到这样一个问答：

没错，因为代码中没有对i和j进行限制，所以它们会一直增长，知道超过int边界，此时它们的乘积为负，负数当然是小于n，但是数组中肯定没有这样的地址！最后贴出问题代码供参考：

public class Solution204 {
    public int countPrimes(int n) {
        boolean isPrime[] = new boolean[n];
        for(int i = 0 ; i < n ; i++)
            isPrime[i] = true;
        int num = 0;
        for(int i = 2 ; i < n ; i++){
            if(!isPrime[i])
                continue;
            for(int j = i ; j*i < n ; j++) {
                System.out.println(j * i + " " + n + "  " + i + "  " + j);
                isPrime[j * i] = false;<span style="white-space:pre">	</span>//当i和j很大时，它们的乘积仍然符合n，但是产生了越界异常
            }
        }
        for(int i = 2 ; i < n ; i++)
            if(isPrime[i] == true)
                num++;
        return num;
    }

    public static void main(String[] args) {
        int n = new Solution204().countPrimes(499979);
        System.out.println(n);
    }
}

另外，关于Sieve找质数算法可以看看wiki：

wiki:Sieve of Eratosthenes

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

关于Java数组越界的一个诡异问题【leetcode204】