Prime1 : Getting Runtime error in java

Hi, I tried seive algorithm for printing the no of primes within the limit. I assigned the largestno to the boolean array that may be causing the error. Kindly help me to solve this issue.

enter code here

import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;


class PrimeSeive1 {

	public static void main(String[] args){

		Scanner in=new Scanner(System.in);
		PrintWriter out=new PrintWriter(System.out);

		Integer total=in.nextInt();

		while(total > 0){
			Integer firstNo=in.nextInt();
			Integer lastNo=in.nextInt();
			List<Integer> primeNo=primeSeive(firstNo,lastNo);

			for(int i=0;i<primeNo.size();i++){
				System.out.println(primeNo.get(i));
			}
			total--;
		}

	}

	private static List<Integer> primeSeive(Integer firstNo, Integer lastNo) {

		Boolean num[]=new Boolean[lastNo+2];
		List<Integer> result=new ArrayList<Integer>();

		num[0]=true;
		num[1]=true;
		for(int i=2;i<=lastNo;i++){
			num[i]=false;
		}
		
		for(int i=2;i<=Math.sqrt(lastNo);i++){
			
			for(int j=i+i;j<=lastNo;j=j+i){
				
				if(num[j]==false){
					num[j]=true;
				}
			}
		}
		for(int i=0;i<num.length;i++){
			if(num[i]==false){
				result.add(i);
			}
		}

		return result;
	}
}

You want to allocate 1GB of memory (if the size of Boolean is 1 byte) when lastNo is 1.000.000.000 (10^9)

Boolean num[]=new Boolean[lastNo+2];

Maybe you can try to use int[] and bit operations to reduce the array size, but do you know what is complexicity of these two loops?

for(int i=2;i<=Math.sqrt(lastNo);i++){
    for(int j=i+i;j<=lastNo;j=j+i){
        ...
    }
}

for i = 2 it makes 500M operations, for i = 3 it makes 333M operations and i = 4 it is 250M operations - 2000M operation for one test case while there are 10 in one file? I believe, that we can assume, that 10M operations per seconds is the limit, so you have something like 60M operations to find the answer.

//