JAVA

prime number between given range in java

/* Solution below implements the Sieve of Eratosthenes algorithm
   https://www.geeksforgeeks.org/sieve-of-eratosthenes/
   Space complexity: O(upper)
   Time complexity: O(upper*log(log(upper)))
*/

import java.util.*;
public List<Integer> primesInRange(int lower, int upper) {
	if (lower > upper || upper <= 2) {
    	return new ArrayList<>();
    }
    List<Integer> result = new ArrayList<>();
    boolean[] primes = new boolean[upper];
    for (int p = lower; p <= (int)Math.sqrt(upper); ++p) {
    	if (primes[p] == false) {
        	for (int scan = p*p; scan < upper; scan += p) {
            	primes[scan] = true;
             }
         }
    }
        
	for (int idx = lower; idx < upper; idx++) {
    	if (primes[idx] == false) {
        	result.add(idx);
         }
     }
        
	return result;
}