使用sieve将素数增加到10^8

Question

为什么这段代码只能运行小于10^4的数字？我需要找到所有小于10^8的质数，但这是否显示了arrayindexoutofbound异常？为什么？我知道我们只能创建大小为10^8的数组(如果我错了，请纠正我)，但这甚至不能用于10^5。

 class Prime
    {
        public static void main (String[] args) throws java.lang.Exception
        {
            boolean[] prime = new boolean[100000000];
            prime[2]=true;
            int i;
            for(i=3; i<100000000; i+=2)
                prime[i]=true;
            for(i=3; i<100000000; i++)  
            {
                if(prime[i]==true)
                    for(int j=i*i; j<100000000; j=j+i)
                        prime[j]=false;
            }
            for(i=1; i<100000000; i++)
            {
                if(prime[i]==true)
                System.out.println(i);
            }
        }
    }

Answer 1

问题出在这里：

for(int j=i*i; j<100000000; j=j+i)

由于i最大可达99999999，因此i*i可能高于Integer.MAX_VALUE，这将导致数字溢出。因此，j将被初始化为负值，并且prime[j]将抛出异常。

要解决此问题，您只需添加一个条件，要求j必须为正：

for(int j=i*i; j > 0 && j<100000000; j=j+i)

Answer 2

for(int j=i*i; j<10000; j=j+i)

如果i是10^5，那么j将是10^10，这将导致int类型的溢出( int类型的最大值是2^31 -1= 2147483647)