Sieve of Eratosthenes using Java 8 streams I am learning streams and lambdas in Java 8.

I wanted to implement the classic Sieve of Eratosthenes using lambdas and streams. This is my implementation.

 /**
 * @author Sanjay
 */
class Sieve {
    /**
     * Implementation of Sieve of eratosthenes algorithm using streams and lambdas 
     * It's much slower than the version with traditional for loops
     * It consumes much memory than the version with traditional for loops
     * It computes all primes upto 100_000_000 in 2 secs (approx) 
     */
    public static List&lt;Integer&gt; sieveOfEratosthenes(int _n) {
        // if _n is empty return an empty list
        if (_n &lt;= 1) return Arrays.asList();
        // create a boolean array each index representing index number itself
        boolean[] prime = new boolean[_n + 1];

        // set all the values in prime as true
        IntStream.rangeClosed(0, _n).forEach(x -&gt; prime[x] = true);
        // make all composite numbers false in prime array
        IntStream.rangeClosed(2, (int) Math.sqrt(_n))
                .filter(x -&gt; prime[x])
                .forEach(x -&gt; unsetFactors(x, prime, _n));
        // create a list containing primes upto _n
        List&lt;Integer&gt; primeList = new ArrayList&lt;&gt;((_n &lt; 20) ? _n : (_n &lt; 100) ? 30 : _n / 3);
        // add all the indexes that represent true in prime array to primeList
        IntStream.rangeClosed(2, _n).filter(x -&gt; prime[x]).forEach(primeList::add);
        // return prime list
        return primeList;
    }

    /*
     * makes all the factors of x in prime array to false
     * as primes don't have any factors
     * here x is a prime and this makes all factors of x as false
     */
    private static void unsetFactors(int x, boolean[] prime, int _n) {
        IntStream.iterate(x * 2, factor -&gt; factor + x)
                .limit(_n / x - 1)
                .forEach(factor -&gt; prime[factor] = false);
    }
}


What is its efficiency compared to normal for-loops?
Are there any imporvements to be made?
Implementation

You can invert the values for prime and not prime to avoid the initial rangeClosed(0, _n).forEach(x -&gt; prime[x] = true). The innermost loop can start at x*x instead of x*2:

// (1)
public static List&lt;Integer&gt; sieveOfEratosthenes(int n) {
    boolean[] notPrime = new boolean[n + 1];

    IntStream.rangeClosed(2, (int) Math.sqrt(n))
            .filter(x -&gt; !notPrime[x])
            .forEach(x -&gt; {
                IntStream.iterate(x * x, m -&gt; m &lt;= n, m -&gt; m + x)
                        .forEach(y -&gt; notPrime[y] = true);
            });

    List&lt;Integer&gt; list = new ArrayList&lt;&gt;();
    IntStream.rangeClosed(2, n)
            .filter(x -&gt; !notPrime[x])
            .forEach(x -&gt; list.add(x));
    return list;
}


This implementation still feels like a literal translation of the for-loop approach. Streams offer options to improve readability, i.e. the inner loop can be flattened:  

// (2)
public static List&lt;Integer&gt; sieveOfEratosthenes(int n) {
    boolean[] notPrime = new boolean[n + 1];

    rangeClosed(2, (int) Math.sqrt(n))
            .filter(x -&gt; !notPrime[x])
            .flatMap(x -&gt; iterate(x * x, m -&gt; m &lt;= n, m -&gt; m + x))
            .forEach(x -&gt; notPrime[x] = true);

    return rangeClosed(2, n)
            .filter(x -&gt; !notPrime[x])
            .boxed().collect(toList());
}


Stream vs Loop

The main problem I see with a stream based approach is (besides the overhead of the streams), that it is more difficult to optimize compared to a loop approach as the abstraction level is higher. For example converting the implementation to a parallel approach is in my opinion way more complicated with a stream approach.

Algorithm improvements (not directly related to the question)

You can use a BitSet (or directly a long/int/byte array) to ensure that each entry in the sieve consumes only one bit (instead of currently (likely) 8). You are storing all values from 2 to n in the sieve, you can save memory by skipping multiples of 2 (and 3, 5, ...) at the cost of some additional calculations to convert between sieve position and value.

For larger values of n it might be advantageous to divide the sieving process in smaller steps and use a small array instead of a large array for all values and sieving the complete range at once.

The sieving process can be converted to a parallel implementation with nearly linear speedup as two or more values can be sieved simultaneously (sieving process of each value is independent from other values).

Approx. performance for n=100_000_000, included my implementation (which utilizes most of the improvements mentioned above) as reference value:

// 1 Thread
Initial            3406676978ns
Version (1)        2487619662ns
Version (2)        2459434320ns
For loop           2158261344ns
Nevay to List      1436579484ns
Nevay to Sieve     1040829243ns
// 8 Threads
Nevay to List       682085628ns
Nevay to Sieve      172952467ns