Главное число между данным диапазоном на 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;
}
Wissam