Runtime error in PrimeNumber Generator on SPOJ

Question

I was trying to solve the PrimeNumber Generator problem on SPOJ. The code always giving runtime error on SPOJ, but in ideone.com it is working fine. Don't know what is causing the issue. I tried both Scanner and BufferedReader for reading inputs.

import java.lang.*;
import java.io.*;

class Main
{
    public static void main (String[] args) throws java.lang.Exception
    {
        BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(r.readLine());
        while (t > 0) {
            String input = r.readLine();
            int N1 = Integer.parseInt(input.split(" ")[0]);
            int N2 = Integer.parseInt(input.split(" ")[1]);
            boolean isPrime[] = new boolean[N2 + 1];
            int count = 0;
            int primes[] = new int[N2 + 1];
            for (int i = 2; i <= N2; i++) {
                isPrime[i] = true;
            }
            for (int i = 2; i * i <= N2; i++) {
                if (isPrime[i]) {
                    for (int j = 2; i * j <= N2; j++) {
                        isPrime[i * j] = false;
                    }
                }
            }
            for (int i = 2; i <= N2; i++) {
                if (isPrime[i]) {
                    primes[count++] = i;
                }
            }
            for (int i = 2; i <= N2; i++) {
                isPrime[i] = true;
            }
            for (int i = 0; i < count; i++) {
                int p = primes[i];
                int s = N1 / p;
                s = s * p;
                for (int j = s; j <= N2; j = j + p) {
                    if (j < N1) {
                        continue;
                    }
                    isPrime[j - N1] = false;
                }
            }

            for (int i = 0; i < count; i++) {
                if (primes[i] >= N1 && primes[i] <= N2) {
                    System.out.println(" " + primes[i]);
                }
            }
            for (int i = 0; i < (N2 - N1 + 1); i++) {
                if (isPrime[i] == true && (i + N1) != 1) {
                    System.out.println(i + N1);
                }
            }
            System.out.println("");
            t--;
        }
    }
}

The sample input I have given is

2
10 30
50 100

I found that the error is at line boolean isPrime[] = new boolean[N2 + 1]. N2 can not able to take value upto 1000000000.

Can somebody help me to resolve this ?

score 1 · Answer 1 · answered Aug 07 '15 at 11:47

You are using a boolean array: int primes[] = new int[N2 + 1]; for your Sieve of Eratosthenes. To save space use bits instead of booleans, a bitSet for instance. To save even more space only record the answer for odd numbers, all evens (except 2) are composite so they can be ignored as long as you make special arrangements for 2; perhaps something like:

if (num % 2 == 0) { return num == 2; }

near the start of your isPrime() method. That will halve the storage space needed.

score 0 · Answer 2 · edited May 23 '17 at 12:14

It looks like you run out of heap memory. Here you have more specific description on how does the heap size impacts your implementation.

One of ways to handle this is to change heap size

-Xms<size>        set initial Java heap size
-Xmx<size>        set maximum Java heap size
-Xss<size>        set java thread stack size

More info here

But I am not sure whether it is possible to do that on SPOJ.

Other way to solve this is to manage the heap usage by splitting this huge array you are declaring and working on smaller ones but multiple times, also after handling single sub-array you need to unreference this array and call System.gc().

Hope it helps:)

So is their any way to overcome this issue ? Do i need to change the initialization statement ? — Sarath S Nair, Aug 07 '15 at 09:37

score 0 · Answer 3 · answered Aug 07 '15 at 12:09

0

Instead of

boolean[] isPrime = new boolean[N2 + 1];

You could do

BitSet isPrime = new BitSet(N2 + 1);

if (!isPrime.get(i)) {
    isPrime.set(i, true);
}

which is a huge reduction of memory, though slower.

answered Aug 07 '15 at 12:09

Joop Eggen

107,315
7
83
138

Runtime error in PrimeNumber Generator on SPOJ

3 Answers3