Open
+ 2

# Can someone help me with TLE (time limit exceed) in java?

i have code with for loop nearly 2000000 iteratons with nested if statement which is calling method with nearly as much itrration in every forloop iteration. how to simplify this https://code.sololearn.com/c4PEhKXU6Xar/?ref=app

4th Mar 2018, 1:55 PM
wolfsan
+ 20
@wolfsan Use SieveOfEratosthenes which is the best algorithm for finding prime numbers in a large range. https://code.sololearn.com/csoPRUTZ7B5H/?ref=app
8th Mar 2018, 11:57 PM
LukArToDo
+ 5
Once i squared is greater than n, no other value of i needs to be tested as the other factor was already processed so: for (int i = 2; i*i < n; i++) Don't bother testing evens so outer loop i+=2 increment.
4th Mar 2018, 2:25 PM
John Wells
+ 5
You share server and only get 4 seconds elapsed time here so not much can be done on this platform. However, if you remember the primes in an array, you only need to test them not any of the numbers between.
4th Mar 2018, 3:02 PM
John Wells
+ 4
I dropped your maximum down to the point it sometimes works here and added my fixes. https://code.sololearn.com/c03ZHyOgAd9r
4th Mar 2018, 2:41 PM
John Wells
+ 2
@john thanks a lot, this helps me at some point in this particular problem, but I am wandering is there a different approach that can be used for even larger loops?
4th Mar 2018, 2:50 PM
wolfsan
+ 2
# john i found a mistake in your solution when an number is sent to method isPrime it somehow skip cheking number and return true. i=2 2*2=4 n=3 just skip for loop and return false I manage to fix this putin in for loop puting i*i<n+1 or i*i<=n and now is good to go. thanks a lot again.
4th Mar 2018, 3:10 PM
wolfsan