Java 8: streams and a sieve of eratosthenes

Question

Eratosthenes sieve can be implemented very carefully in Haskell, using laziness to create an endless list, and then remove all multiple chapters of the list from its tail:

primes :: [Int]
primes = sieve [2..]
sieve (x:xs) = x : sieve [y | y <- xs, y `mod` x > 0]

I am trying to learn about the use of threads in Java 8, but I will find out if there is a way to achieve the same result in Java as the Haskell code above. If I consider a lazy Haskell list as the equivalent of a Java thread, it seems that I need to take a thread led by 2 and create a new thread with all multiples of 2 removed, and then take this thread and create a new thread with all multiples of 3 removed and ...

And I have no idea how to act.

Is there a way to do this, or am I kidding myself when I try to think of Java threads comparable to Haskell lists?

Answer 1

Of course, this is possible, but greatly complicated by the fact that Java threads do not have an easy way to decompose into the head and tail (you can easily get either one of them, but not so, since the thread will already have been absorbed by then - it seems that someone can use linear types ...).

The solution is to save a mutable variable. For example, this mutable variable may be a predicate that checks if a number is a multiple of any other number that has been shown 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 will get the expected result:

$ javac Primes.java
$ java Primes
2
3
5
7
11
13
17
19
23
29

Answer 2

If you decide to make a Scala decision, 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))

, Haskell, IMO. :

scala> primes take 10 foreach println
2
3
5
7
11
13
17
19
23
29

Scala Stream - , , Java 8 Stream. , Haskell zipWith.

Answer 3

: , ,

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();
}

:

public static void main(String[] args) {
    primeStreamEra().forEach(i -> System.out.println(i));
}

:

, ( ).

3 .

:

• , / sqrt (currentNumber), .
• , false.
• true.

:

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);
}

:

public static void main(String[] args) {
    System.out.println(Arrays.toString(primeStream(50).toArray()));
}

: [1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

: IntStream Stream<Integer> primeStream(50).boxed().

Answer 4

?

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);
        }
    }
}

Answer 5

Collector.

  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);
  }

:

  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);
  }

( Java 9 TakeWhile O (n) 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
        );