使用筛子得到 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<10000; j=j+i)

如果i是10^5，那么j就是10^10，对于int类型会造成溢出（int类型的最大值是2^31 - 1 = 2147483647）

Answer 2

问题在这里：

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)

使用筛子得到 10^8 以内的素数

Prime numbers upto 10^8 using sieve

java

arrays

primes

sieve-of-eratosthenes