Prime Visits : tle error

#1

time limit error

import java.util.Scanner;

public class Main {
static Scanner scn = new Scanner(System.in);

public static void main(String[] args) {
	// no of test cases
	int N = scn.nextInt();

	while (N > 0) {
		// range of cities
		int loLim = scn.nextInt();
		int upLim = scn.nextInt();
		int citiesVisited = SieveOfErathosthenes(loLim, upLim);
		System.out.println(citiesVisited);
		N--;
	}
}

public static int SieveOfErathosthenes(int low, int high) {
	int counter = 0;
	// sieve
	boolean[] isPrime = new boolean[high+1];
	isPrime[0] = false;
	isPrime[1] = false;
	for (int i = 2; i < isPrime.length; i++) {
		isPrime[i] = true;
	}

	for (int p = 2; p * p <= isPrime.length; p++) {
		if (isPrime[p] == true) {
			for (int i = p * p; i < isPrime.length; i += p) {
				isPrime[i] = false;
			}
		}
	}

	// all primes in range
	for (int i = low; i <= high; i++) {
		if (isPrime[i] == true) {
			counter++;
		}
	}
	return counter;
}

}

#2

This code will give TLE (Time Limit Exceeded) error because in your code the loop runs separately for each test case to calculate number of prime numbers in given range. You are making sieve for each test case again and again.
So the total iterations exceed 10^8 in worst case, according to the given constraints. Hence it gives TLE.

More optimized approach is to pre compute the prime numbers in the range given in question and then traverse that array for each test case.

I would highly recommend you to go through videos of Time and Space Complexity given in the course!!!