All test cases true but cant think of TLE solution

#1


my code how to solve TLE

#2

@HemantNasa Hi, basically what you can do is precompute the primes first, you can use sieve of eratosthenes, what it will do is it will reduce the overhead of finding primes for every test case then you can make a list of primes in one go and then query it for each test case.

Its the best approach. Also your input format is not correct either, first take multiple test case input.
If you have doubt lemme know, if you don’t know about sieve read about it!

#3

I solved the same question using that too let me show my code

#4

@HemantNasa Also your input format is not correct either, first take t test cases as input.

#5

https://ide.codingblocks.com/s/247721 see this but still tle showed

#6

https://ide.codingblocks.com/s/247895 out of 5 test cases only first test case TLE rest of are passes. Will you please help

#7

@HemantNasa Bro when you are precomputing primes upto 10^6, do one think precompute the list containing only primes using the above primes array, the thing is you are querying for every test case and computing with a loop, so when test cases are very large it will give you a tle.

So precompute the list containing only primes like this:-

ArrayList list = new ArrayList();
for(int i = 2; i < primes.length; i++) {
if(primes[i]) {
list.add(i);
}
}

Now you can query this list in O(1). If you have doubt lemme know bro!

#8

its solved thanks bro for this… Gonna give you 5 rating thanks a lot