CODEWITHSUNDEEP
javaarraysprimessieve-of-eratosthenes
Prashant
Prashant

Reputation: 33

Prime numbers upto 10^8 using sieve

Why this code is working only number less than 10^4? i need to find all the prime numbers less than 10^8 but this is showing arrayindexoutofbound exception? why? i know we can only create array till size10^8(correct me if i am wrong) but this is not even working for 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);
            }
        }
    }

Upvotes: 1

Views: 604

Answers (2)

Eran
Eran

Reputation: 393831

The problem is here:

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

Since i can be as large as 99999999, i*i may be higher than Integer.MAX_VALUE, which will cause numeric overflow. As a result, j will be initialized to a negative value, and prime[j] will throw an exception.

To fix the problem, you can simply add a condition that requires the j must be positive:

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

Upvotes: 2

Hưng Chu
Hưng Chu

Reputation: 1052

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

if i is 10^5, then the j would be 10^10, which would cause overflow for int type (max value of int type is 2^31 - 1 = 2147483647)

Upvotes: 0

Related Questions