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

Question

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

Answer 1

@wolfsan
Use SieveOfEratosthenes which is the best algorithm for finding prime numbers in a large range.

https://code.sololearn.com/csoPRUTZ7B5H/?ref=app

Answer 2

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.

Answer 3

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.

Answer 4

I dropped your maximum down to the point it sometimes works here and added my fixes.
https://code.sololearn.com/c03ZHyOgAd9r

Answer 5

@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?

Answer 6

# 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.