Prateek loves candy2

#1

used sieve of eratosthenes to find the nth prime number but is showing time limit please help me to optimize the code

package challenges;

import java.util.Scanner;

public class prateklovescandy2 {

public static void main(String[] args) {
	Scanner scan=new Scanner(System.in);
	int T=scan.nextInt();
	
	boolean flag=true;
	for(int p=1;p<=T;p++)
	{
		flag=false;
	boolean[] isprime=new boolean[1000001];
	int N=scan.nextInt();
	for(int a=1;a<=1000000;a++)
	{
		isprime[a]=true;
		
	}

	
	for(int i=2;i<=1000000;i++)
	{
		isprime[1]=false;
		if(isprime[i]==true)
		{
			
			for(int j=2;i*j<=1000000;j++)
			{
				
				isprime[i*j]=false;
				
			}
		
		
		}
	
	
	}
	int counter=0;

for(int i=0;i<isprime.length;i++)
{
if(isprime[i]==true)
{
counter++;
if(counter==N)
{
System.out.println(i);
flag=true;
break;
}
if(flag==true)
{
break;
}

}
if(flag==true)
{
	break;
}

}

	}
}

}

#2

yaa it will give tle because for each test case you are using sieve…take the logic of seive outside the for loop…it means that you pre compute the prime numbers and store it somewhere(arraylist)…and then when user enter N you just get the corresponding value from ArrayList…

#3

tried the way you said still facing the same issue

#4

package challenges;

import java.util.Scanner;

public class prateklovescandy2 {

public static void main(String[] args) {
	Scanner scan=new Scanner(System.in);
	
	
	
	boolean[] isprime=new boolean[1000001];
	
	for(int a=1;a<=1000000;a++)
	{
		isprime[a]=true;
		
	}

	
	for(int i=2;i<=1000000;i++)
	{
		isprime[1]=false;
		if(isprime[i]==true)
		{
			
			for(int j=2;i*j<=1000000;j++)
			{
				
				isprime[i*j]=false;
				
			}
		
		
		}
	
	
	}
	int T=scan.nextInt();
	
	for(int p=1;p<=T;p++)
	{
		int N=scan.nextInt();
	int counter=0;
	boolean flag=true;
	
	flag=false;

for(int i=0;i<isprime.length;i++)
{
System.out.println(i+“i”);
if(isprime[i]==true)
{
counter++;
if(counter==N)
{
System.out.println(i);
flag=true;
break;
}
if(flag==true)
{
break;
}

}

if(flag==true)
{
	break;
	}

}

	}
}

}

#5

besides how to store in a arraylist since how can i be sure that first n primenumbers will have certain limit so used array to store all numbers
boolean[] isprime=new boolean[1000001];

#6

traverse through the isPrime array if the number is prime add in arrayList…u can hit and trial and see the upper bound till you get all prime numbers

#7

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.