private static List<Integer> primeSieve(int n) {
        List<Integer> primes = new ArrayList<>();
        // minFact[i] contains the minimum prime factor of i.
        int[] minFact = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            if (minFact[i] == 0) {
                primes.add(i);
                minFact[i] = i;
            }
            // Find multiples of i where primes[j] is the minimum prime factor. This loop will go exactly once for each
            // composite number. How it works: given a number i with prime factorization p1*...*pn, where p1<=...<=pn,
            // we say that, for each prime p <= p1, the number i*p is composite with minimum prime factor p.
            // Why this gets to every number exactly once: the number p1*...*pn will be generated only by p2*...*pn.
            // That's because all of it's prime factors need to be higher than it.
            for (int j = 0; j < primes.size() && primes.get(j) <= minFact[i] && i * primes.get(j) <= n; ++j) {
                minFact[i * primes.get(j)] = primes.get(j);
            }
        }
        return primes;
    }