Big Array in JAVA

Question

I am trying to solve Spoj prime generator using Sieve Of Eratosthenes But am getting NZEC error. Can anybody help me . Some users have said using sieve already would help me .

import java.util.*;
public class Main
{
    public static void main (String args[])
    {
        Scanner sc =new Scanner(System.in);
        int n =sc.nextInt();
        int g,h;
        int isPrime[]=new int[1000000000];
        for (int j=3;j<1000000000;j++)
        {
            isPrime[0]=0;
            isPrime[1]=0;
            isPrime[2]=1;
            if(j%2==0)
                isPrime[j]=0;
            else
            isPrime[j]=1;
        }
        for(int k=3;k<=Math.sqrt(1000000000);k=k+2)
        {
            if(isPrime[k]==1)
                for (int l=k*k;l<1000000000;l=l+k)
            {
                isPrime[l]=0;
            }
        }
        for (int i=0;i<n;i++)
        {
            g =sc.nextInt();
            h =sc.nextInt();
            for (int m=g; m<=h;m++)
            {
                if(isPrime[m]==1)
                    System.out.println(m);
            }
            System.out.println();
        }
        System.exit(0);
    }
}`

Consider changing `int isPrime[]` to `boolean isPrime[]`. That way you will use 4 times less memory — Fureeish, Dec 26 '18 at 13:51
@nicomp care to elaborate? As far as I know, the sizes of primitives are fixed, no matter what. The sizes of references, however, are dependant on architecture. Can you provide any examples where the size of `int` is not `4` and the size of `boolean` is not `1`, in terms of bytes? — Fureeish, Dec 26 '18 at 13:58
It's the difference between abstraction and actual implementation. Many JVM implementations at the VM level handle data in 32-bit chunks or frames. When data goes onto the virtual machine stack, it occupies one of the frames (unless it's a long or double, then 2 frames). At the VM level, a `byte`, `boolean`, and `int` occupy the same number of frames. About the only time a `byte` will save real space over an `int` is when it's allocated onto the heap as an array. — scottb, Dec 26 '18 at 14:17
@scottb "*About the only time a `byte` will save real space over an `int` is when it's allocated onto the heap as an array*" - which is exactly the case here, unless you specifically meant just `byte` and just `int`. We're dealing with heap-allocated arrays of `int`s and `boolean`s. [Here](https://softwareengineering.stackexchange.com/a/363294) I can see that arrays of `boolean` have specific support, but I am unable to fully understand it. Do you claim that allocated `n` integers will occupy the same size as allocated `n` booleans? — Fureeish, Dec 26 '18 at 14:23
The number of bits used to represent a `boolean` is not specified as part of the JLS and is implementation dependent. Applications should not be written to depend upon booleans having a specified size. They may be implemented as 32 bit integers (which is the size of a stack frame). — scottb, Dec 26 '18 at 14:36
@scottb Do you know any production-quality JVM where boolean arrays occupy more than 1 byte per element? — Ralf Kleberhoff, Dec 26 '18 at 15:28
@RalfKleberhoff: I don't know of any,. But even if there weren't any, it would be a mistake to code as though there wouldn't ever be any. — scottb, Dec 27 '18 at 15:22
It'll never be a mistake to make it a `boolean[]` array, even if it doesn't save space over an `int[]` in some implementations. — Ralf Kleberhoff, Dec 27 '18 at 16:38

score 0 · Answer 1 · answered Dec 26 '18 at 14:04

Simple sieve may not run in the given time limit. At least it didn't for me. The better approach is segmented sieve. Here are few links that may help you:

stackoverflow

primesieve

I used the second link to understand and solve the question. But the first link also has a good explanation. Go through both of them and you should be able to solve the problem. Happy Coding!

P.S: You seem to be using Scanner for reading input. It will be very slow. Use BufferedReader to speed up the reading of inputs. In websites like SPOJ, it is very crucial.

Thanks . I use Buffered Reader but I dont know how to take single line input using BufferedReader . — Giri Nath, Dec 26 '18 at 17:01

Oleg Cherednik · Answer 2 · 2018-12-26T14:52:57.433

Only reason is just JVM should have enough space to store new boolean[total + 1] about 4Gb:

public static void main(String... args) {
    boolean[] primes = primes(1_000_000_000);

    try (Scanner scan = new Scanner(System.in)) {
        int n = scan.nextInt();

        for (int i = 0; i < n; i++) {
            int from = scan.nextInt();
            int to = scan.nextInt();

            for (int j = from; j <= to; j++)
                if (primes[j])
                    System.out.println(j);

            System.out.println();
        }
    }
}

private static boolean[] primes(int total) {
    // initially assume all integers are primes
    boolean[] primes = new boolean[total + 1];
    Arrays.fill(primes, true);
    primes[0] = false;
    primes[1] = false;

    // mark non-primes <= total using Sieve of Eratosthenes
    for (int i = 2; i * i <= total; i++) {
        // if i is primes, then mark multiples of i as nonprime
        // suffices to consider mutiples i, i+1, ...,  total/i
        if (!primes[i])
            continue;
        for (int j = i; i * j <= total; j++)
            primes[i * j] = false;
    }

    return primes;
}

Big Array in JAVA

2 Answers2