How to solve TLE?

#1

I have tried my best to optimize the code ,but still failed to get pass through 1 test case . Can you please guide me a better approach to optimize this code

import java.util.*;
public class Main {
public static void main(String args[]) {
Scanner scan = new Scanner(System.in) ;
int n = scan.nextInt() ;

	while(n-- > 0){
		int choco = scan.nextInt() ;
		int count = 0 ;
		int latest = 0 ;
		boolean isPrime ;
		for(int i =2 ; count != choco ; i++){
			isPrime = true ;
			for(int j = 2 ;j <= Math.sqrt(i) ; j++){
				if(i % j == 0){
					isPrime =false ;
					break ;
				}
			}
			if(isPrime){
				
				count ++ ;
				if(count == choco){
					latest = i ;
					break ;
				}
			}
		}
		System.out.println(latest) ;
	}
}

}

Compiler is showing that i have used brute force approach,I don’t know what is brute force ,Can you explain me what is brute force and also which approach is better than brute force?

#2

Main logic behind the question is that you need to find the nth prime number starting from 2. Any one can implement this logic “Not a big Deal” for anyone, but wait a min there’s more to it.

Many of you are getting time limit exceed right ? Even if you are using SOE (Sieve of Eratosthenes) for finding the prime numbers.

Have u see the constraint on number of test cases, It’s quite large because for every test case you are going to find the prime numbers upto that number and at last return the last prime number found, this will cause the TLE for big test cases.

So, to overcome this problem, let’s just store your test cases in an array.
Then find the maximum number from all of the testcases.
then, Use SOE(Sieve of Eratosthenes) to find the prime number upto that number and store that an the array.
After storing, simply loop over every test case that was stored previously in an array.
Print the value of n from the array storing primes.
That’s how we need not to find the prime number for every test case. :slight_smile:

#3

@Lalit2142
please mark your doubt as resolved and rate my work as well

#4

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.

#5

@Lalit2142,

You are supposed to use the prime seive optimisation technique. Also make sure that you call the primeseive function that you will make before the test cases only to prevent TLE.

Precompute the prime numbers using sieve technique.

In the sieve technique where you create a boolean array of b+1 size.

And start from the first prime number i.e. 2. Take its square(4) and increment it by the number you took (i.e. 4,6,8,10 and so on). Mark all these as false since they cannot be primes.

Now take the next unmarked number, 3. And mark 9,12,15 and so as false. Similarly do it for 4. 16,20,24 and so on as false.

When you finish the loop, count all the positions marked as true and when count is equal to the given test case value print that index. This will be our final answer.

Brute force is something relying on or achieved through the application of force, effort, or power in usually large amounts instead of more efficient methods. Your method is brute force because you are checking for every number instead of using an efficient algorithm

#6

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.