How is this Eratosthenes Sieve implementation is working internally?

Question

I found this code that seems to be the non-optimal version of the Sieve of Erastothenes, it gets the N first prime numbers into an array.

private IntPredicate p = x -> true;

private int[] primes(int n) {
    
    return IntStream.iterate(2, i -> i + 1)
        .filter(x -> p.test(x))
        .peek(i -> p = p.and(k -> k % i != 0))
        .limit(n)
        .toArray();
}

What's happening internally with the IntPredicate?

@AlexanderIvanchenko actually if I just put a true literal in the filter method or just delete the filter method at all, I get a different input, may be I should add the output result. — Brando Jeanpier, Oct 20 '22 at 17:30
I didn't see that the predicate is being altered by `peek()` because of the formating. — Alexander Ivanchenko, Oct 20 '22 at 17:42
obligatory notice that this is *not* the sieve of Eratosthenes, but rather the non-optimal version of the sieve of trial division by primes. — Will Ness, Oct 21 '22 at 17:35
@WillNess how would it be the optimal version of the sieve of Erastothenes? I couldn't find an implementation in Java. — Brando Jeanpier, Oct 22 '22 at 04:43
optimal trial division test-divides each number by all the primes not exceeding the number's square root. your version test-divides each number by all the primes smaller than the number itself (which is, all the primes discovered thus far in the iteration). see more [here](https://stackoverflow.com/search?tab=votes&q=postponed%20user%3a849891). and again, these are _not_ sieves of _Eratosthenes_, which does _not_ test-divide numbers at all but instead counts up from a discovered prime in steps of that prime and _thus_ discovers that prime's multiples: (contd.) — Will Ness, Oct 22 '22 at 09:05
... ``primes = [2,3,...] `set-minus` [[2p,3p,...] FOR p IN primes]``. — Will Ness, Oct 22 '22 at 09:05
@Brando Jeanpier you can find a Java implementation of the Sieve of Eratosthenes in the middle of [this answer](https://stackoverflow.com/questions/48754107/making-a-parallel-intstream-more-efficient-faster/48764124#48764124:~:text=Sieve%20of%20Eratosthenes) — Holger, Oct 25 '22 at 07:59

score 4 · Answer 1 · edited Oct 21 '22 at 17:29

This code produces an aggregate Predicate via IntPredicate.and() method, which would work this way:

p = x -> true; // for first stream element `2` - 
               //   which passes the predicate p

// Predicate p is being reassigned while
// peek() sees the element `2`, to
p = x -> true && x % 2 != 0

// The next stream element `3` passes the updated predicate
// And the predicate is being reassigned again while
// peek() sees the element `3` to

p = x -> true && x % 2 != 0 && x % 3 != 0

// And so on...

So every element which successfully passes the filter results in a new condition being appended to the current predicate via "logical AND" &&.

At the end of the stream execution, the predicate would consist of conditions that check the given number against all the prime number from that would be present in the result.

Note that this hacky implementation is broken:

peek() is an operation which was introduced exclusively to support debugging. It's not meant to be used for performing actions that could affect the result of the execution. peek gives no guaranty regarding the order in which it will be called while executing in parallel, and in certain cases can be optimized away.

How is this Eratosthenes Sieve implementation is working internally?

1 Answers1