Reputation: 548
Java 8: streams and the Sieve of Eratosthenes
The Sieve of Eratosthenes can be implemented very neatly in Haskell, using laziness to generate an infinite list and then remove all multiples of the head of the list from its tail:
primes :: [Int]
primes = sieve [2..]
sieve (x:xs) = x : sieve [y | y <- xs, y `mod` x > 0]
I'm trying to learn about using streams in Java 8, but I figure out if there's a way of achieving the same result in Java as the Haskell code above. If I treat a Haskell lazy list as equivalent to a Java stream, it seems that I need to take a stream headed by 2 and produce a new stream with all multiples of 2 removed, and then take that stream and produce a new stream with all multiples of 3 removed, and...
And I have no idea how to proceed.
Is there any way of doing this, or am I deluding myself when I try to think of Java streams as comparable to Haskell lists?
Upvotes: 9
Views: 2699
Answers (6)
Reputation: 21434
Here's a solution using the Stream Gatherers feature in the upcoming Java 24:
List<Integer> primes = IntStream.rangeClosed(2, 100).boxed()
.gather(Gatherer.<Integer, List<Integer>, Integer>ofSequential(
ArrayList::new,
Gatherer.Integrator.ofGreedy((state, element, downstream) -> {
for (int prime : state) {
if (element % prime == 0) {
return true;
}
}
downstream.push(element);
state.add(element);
return true;
})))
.toList();
This uses an ArrayList<Integer> of found primes as the gatherer's state, and an integrator that checks each element against the primes found thus far. Whenever a new prime is found, it is both pushed to the resulting stream and added to the list of found primes.
Upvotes: 0
Reputation: 1940
An alternative solution, you can implement the Collector interface.
public static void main(String[] args)
{
Collector<Integer, List<Integer>, List<Integer>> sieve = new Collector<Integer, List<Integer>, List<Integer>>()
{
@Override
public Supplier<List<Integer>> supplier()
{
return ArrayList::new;
}
@Override
public BiConsumer<List<Integer>, Integer> accumulator()
{
return (prevPrimes, candidate) ->
{
if (prevPrimes.stream().noneMatch(p -> candidate % p == 0))
{
prevPrimes.add(candidate);
}
};
}
@Override
public BinaryOperator<List<Integer>> combiner()
{
return (list1, list2) ->
{
list1.addAll(list2);
return list1;
};
}
@Override
public Function<List<Integer>, List<Integer>> finisher()
{
return Function.identity();
}
@Override
public Set<Characteristics> characteristics()
{
Set<Characteristics> set = new HashSet<>();
set.add(Characteristics.IDENTITY_FINISH);
return set;
}
};
List<Integer> primesBelow1000 = IntStream.range(2, 1000)
.boxed()
.collect(sieve);
primesBelow1000.forEach(System.out::println);
}
More concisely:
public static void main(String[] args)
{
List<Integer> primesBelow1000 = IntStream.range(2, 1000)
.boxed()
.collect(
ArrayList::new,
(primes, candidate) ->
{
if (primes.stream().noneMatch(p -> candidate % p == 0))
{
primes.add(candidate);
}
},
List::addAll
);
primesBelow1000.forEach(System.out::println);
}
More efficient (using Java 9 TakeWhile to change O(n) to O(sqrt(n))):
List<Long> primesBelowLimit = LongStream.range(2, below)
.collect(
ArrayList::new,
(primes, candidate) ->
{
long candidateRoot = (long) Math.sqrt(candidate);
if (primes.stream()
.takeWhile(p -> p <= candidateRoot)
.noneMatch(p -> candidate % p == 0))
{
primes.add(candidate);
}
},
List::addAll
);
Upvotes: 1
Reputation: 41
EDIT: The sieve, unoptimised, returning an infinite stream of primes
public static Stream<Integer> primeStreamEra() {
final HashMap<Integer, Integer> seedsFactors =
new HashMap<Integer, Integer>();
return IntStream.iterate(1, i -> i + 1)
.filter(i -> {
final int currentNum = i;
seedsFactors.entrySet().parallelStream()
.forEach(e -> {
// Update all factors until they have
//the closest value that is >= currentNum
while(e.getValue() < currentNum)
e.setValue(e.getValue() + e.getKey());
});
if(!seedsFactors.containsValue(i)) {
if(i != 1)
seedsFactors.put(i, i);
return true;
}
return false;
}).boxed();
}
Test:
public static void main(String[] args) {
primeStreamEra().forEach(i -> System.out.println(i));
}
Initial Post:
A somewhat simpler solution that avoids some unnecessary operations (such as testing even numbers).
We iterate all odd numbers from 3 until the limit.
Within the filter function:
- We test for all primes we have found that are smaller/equal than sqrt(currentNumber) rounded down.
- If they divide our current number return
false. - Else add to the list of found primes and return
true.
Function:
public static IntStream primeStream(final int limit) {
final ArrayList<Integer> primes = new ArrayList<Integer>();
IntStream primesThreeToLimit =
IntStream.iterate(3, i -> i + 2)
.takeWhile(i -> i <= limit)
.filter(i -> {
final int testUntil = (int) Math.sqrt((double) limit);
for(Integer p: primes) {
if(i % p == 0) return false;
if(p > testUntil) break;
}
primes.add(i);
return true;
});
return IntStream.concat(IntStream.of(1,2), primesThreeToLimit);
}
Test:
public static void main(String[] args) {
System.out.println(Arrays.toString(primeStream(50).toArray()));
}
Output: [1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
Edit: To convert from IntStream to Stream<Integer> just do primeStream(50).boxed().
Upvotes: 2
Reputation: 9
May be such solution?
public class ErythropheneSieveFunctionBitSet implements IntFunction<BitSet> {
@Override
public BitSet apply(int value) {
BitSet set = new BitSet();
fillSet(set, value);
int s = set.stream().min().getAsInt();
while (s * s <= value) {
int temp = s;
int i = 0;
int multipleTemp;
while ((multipleTemp = s * (s + i)) <= value) {
set.clear(multipleTemp);
i++;
}
s = set.stream().filter(x -> x > temp).min().getAsInt();
}
return set;
}
private void fillSet(BitSet set, int value) {
for (int i = 2; i < value; i++) {
set.set(i);
}
}
}
Upvotes: -1
Reputation: 117
If you'd accept a Scala solution instead, here it is:
def sieve(nums:Stream[Int]):Stream[Int] = nums.head #:: sieve(nums.filter{_ % nums.head > 0})
val primes:Stream[Int] = sieve(Stream.from(2))
It is not as elegant as the Haskell solution but it comes pretty close IMO. Here is the output:
scala> primes take 10 foreach println
2
3
5
7
11
13
17
19
23
29
Scala's Stream is a lazy list which is far lazier than the Java 8 Stream. In the documentation you can even find the example Fibonacci sequence implemantation which corresponds to the canonical Haskell zipWith implementation.
Upvotes: 3
Reputation: 32339
Sure, it is possible, but greatly complicated by the fact that Java streams have no simple way of being decomposed into their head and their tail (you can easily get either one of these, but not both since the stream will already have been consumed by then - sounds like someone could use linear types...).
The solution, is to keep a mutable variable around. For instance, that mutable variable can be the predicate that tests whether a number is a multiple of any other number seen so far.
import java.util.stream.*;
import java.util.function.IntPredicate;
public class Primes {
static IntPredicate isPrime = x -> true;
static IntStream primes = IntStream
.iterate(2, i -> i + 1)
.filter(i -> isPrime.test(i))
.peek(i -> isPrime = isPrime.and(v -> v % i != 0));
public static void main(String[] args) {
// Print out the first 10 primes.
primes.limit(10)
.forEach(p -> System.out.println(p));
}
}
Then, you get the expected result:
$ javac Primes.java
$ java Primes
2
3
5
7
11
13
17
19
23
29
Upvotes: 11
Related Questions
- How is this Eratosthenes Sieve implementation is working internally?
- Using java streams to find if a number is prime or not
- Racket Sieve of Eratosthenes using Stream
- calculating prime numbers (streams and lambdas)
- Sieve of Eratosthenes without arrays?
- Prime Factorization of a Positive Integer with Streams
- Prime numbers by Eratosthenes quicker sequential than concurrently?
- Parallel Sieve of Eratosthenes using Clojure Reducers
- Sieve of Eratosthenes in Java: A Puzzle and some optimization
- Find the prime-->sieve way