prime1 spoj generating prime numbers between two number

Question

package primesieve1;

import java.io.InputStreamReader;
import java.util.Scanner;

public class Primesieve1 {

    public boolean[] sieveOfEratosthenes(int max){

    boolean[] primeno; //defaults to false
        primeno = new boolean[max];
    for(int i=2; i<max; i++ ){primeno[i]=true;}

    for(int i=2; i<Math.sqrt(max);i++){
        if(primeno[i] == true){
            //all multiples of i*i, except i, are not primeno
            for(int j = i + i; j<max; j=j+i){
                primeno[j]=false;
            }
        }

    }
    return primeno;
}

    public void printTrue(boolean[] arr){
    for(int i=0; i<arr.length; i++){
        if(arr[i]==true){
            System.out.print(i + ", ");
        }
    }
    }

    public static void main(String[] args) {

        System.out.println("enter limit");
        Scanner sc = new Scanner(new InputStreamReader(System.in));
     int a = sc.nextInt();
        boolean a1[];
        Primesieve1 obj = new Primesieve1();
        a1 = obj.sieveOfEratosthenes(a);

        obj.printTrue(a1);

    }
}

giving out this error didnt understand why java.lang.OutOfMemoryError: Java heap space

If `max` is really huge, there's not enough room for `primeno = new boolean[max];`... — Dennis Meng, Oct 09 '13 at 05:16
Figure out a way to solve the problem without allocating a gigantic array. — Dennis Meng, Oct 09 '13 at 05:19
if int can take a value upto 1000000000 then why its going outof memory for a boolean array.. — leo, Oct 09 '13 at 05:21
Competition programming problems always have a memory limit; they could easily have set up the testing JVM so that it throws an `OutOfMemoryError` if you go over their bounds. — Dennis Meng, Oct 09 '13 at 05:23
Reading the problem statement, looks like the limit for this problem is 256MB. — Dennis Meng, Oct 09 '13 at 05:24
okeys but its going OutOfMemoryError in my system too i am using netbeans 7.3.1 — leo, Oct 09 '13 at 05:25
okey got it i will try to find other way out 1 more thing how did u find out how much memory the program is using.. — leo, Oct 09 '13 at 05:31
It looked like you were trying to get an array big enough to hold all of the numbers from 1 to the largest input value (1000000000), so that's 1 billion times the size of a boolean. (Note that you could actually be trying to allocate more than that; I assumed booleans were 1 byte, which apparently isn't necessarily true.) — Dennis Meng, Oct 09 '13 at 05:34

score 0 · Accepted Answer · answered Oct 09 '13 at 05:36

0

Although I'm not 100% sure I think a boolean[] still uses about 1 byte per entry. Max will probably get quite big so even increasing the memory for the JVM will probably not do the trick. One thing you can do however is not use a boolean[] but a BitSet instead, this way you'll only use 1 bit per number and thus you can probably cover until the max value of int.

answered Oct 09 '13 at 05:36

Alowaniak

571
3
10

For what it's worth, I hit [this](http://stackoverflow.com/questions/383551/what-is-the-size-of-a-boolean-variable-in-java) question when double checking the size of a `boolean`. – Dennis Meng Oct 09 '13 at 05:43

prime1 spoj generating prime numbers between two number

1 Answers1