Prime1

[vanu]

I m trying to solve prime1 using seive algorithm.
I m getting wrong answer while executing that program in spoj. kindly tell me if I made mistake anywhere .

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

class PrimeSeive {

public static void main(String[] args){
	try{
	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--;
	}
	}catch(Throwable ex){
		ex.printStackTrace();
	}
	
}

private static List<Integer> primeSeive(Integer firstNo, Integer lastNo) {
	
	Boolean num[]=new Boolean[1000000010];
	List<Integer> result=new ArrayList<Integer>();
	for(int i=1;i<num.length;i++){
		num[i]=false;
	}
	for(int i=2;i<num.length;i++){
		for(int j=i+i;j<num.length;j=j+i){
			if(num[j]==false){
				num[j]=true;
			}
		}
	}
	
	for(int i=firstNo;i<num.length;i++){
		if(num[i]!=true){
			result.add(i);
		}
	}
	
	return result;
}

}

[leppyr64]

If you remove the try/catch you will get a runtime error. So you realize how much memory an array as large as num consumes?

[vanu]

yes you are correct. I removed the try catch block. It throwing runtime error. I m getting error java.lang.OutOfMemoryError: Java heap space while creating the boolean array of size 100000000.

Kindly help me. how can I declare the Boolean array of 1000000000.

I have got output till 10000000 . It's throws error once we have given input no as 100000000 and beyond.

thanks in advance.

[leppyr64]

You don't need all of the primes up to 10^9, you need to do a little bit of thinking to understand why.

[vanu]

you are correct leppy. I have got timelimit exceeded when i am executing the below code.

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

class PrimeSeive {

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) {
	
	Integer num[]=new Integer[(lastNo-firstNo)+1];
	List<Integer> result=new ArrayList<Integer>();
	

	for(int i=0,j=firstNo;(i<=num.length && j <= lastNo);i++,j++){
	
		num[i]=j;
	}
	int k=0;
	for(int i=2;i<=lastNo;i++){
		
		for(int j=i+i;j<=lastNo;j=j+i){
		  	while(k<num.length){
		  		
			if(num[k]==j){
				
				num[k]=0;
				break;
			
			
			}	
			else{
				k++;
			}
		  	}
	}
	}
	
	for(int i=0;i<num.length;i++){
		if(num[i]!=0){
			result.add(num[i]);
		}
	}
	
	return result;
}

}

because of the O(n^3) time complexity i think .. can u suggest any other ways to solve this problem. or how to simply this logic.

[leppyr64]

You're on the right track with the sieve, but you need to reduce the complexity of it.

For example this loop alone will cause your TLE.
for(int i=2;i<=lastNo;i++){

Please use code tags when posting code.

[vanu]

I try to minimize the loop . It accepts all the testcases till 10^7.

when I tried with testcase

1
10^7
10^9

it throwing the error

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
at PrimeSeive.primeSeive(Main.java:32)
at PrimeSeive.main(Main.java:20)

here is my code. kindly check whether my logic is correct or not.

import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
class PrimeSeive {
    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) {

	Integer num[]=new Integer[(lastNo/2)];
	List<Integer> result=new ArrayList<Integer>();
            if(firstNo==1)
                    firstNo++;
	for(int i=0,j=firstNo;j<=lastNo;j++){
		if(j%2!=0){
			num[i]=j;
			i++;
		}
	}
	for(int i=3;i<=Math.sqrt(lastNo)+1;i=i+2){
		int j=i+i;
		int k=0;
		while((j<=lastNo)&&(k<num.length)&&(num[k]!=null)){
			if(num[k]==j){
				num[k]=1;
				k++;
				j=j+i;
			}
			else if(num[k]<j){
				k++;
			}
			else if(num[k]>j){
				
				j=j+i;
			}
		}
	}
	
	for(int i=0;((i<num.length)&&(num[i]!=null));i++){
		
		if(num[i]!=1){
			
			result.add(num[i]);
		}
	}

	return result;
}
}