Java 8：溪流和埃拉托色尼筛法

Question

Eratosthenes 筛法可以在 Haskell 中非常巧妙地实现，使用惰性生成一个无限列表，然后从其尾部删除列表头部的所有倍数：

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

我正在尝试学习如何在 Java 8 中使用流，但我想知道是否有一种方法可以在 Java 中实现与上述 Haskell 代码相同的结果.如果我将 Haskell 惰性列表视为等同于 Java 流，那么我似乎需要采用以 2 为首的流并生成一个删除了所有 2 的倍数的新流，然后采用该流stream 并产生一个新的流，删除了所有 3 的倍数，并且...

我不知道如何继续。

有什么方法可以做到这一点，或者当我试图将 Java 流与 Haskell 列表相提并论时，我是在自欺欺人吗？

Answer 1

当然，这是可能的，但由于 Java 流没有简单的方法可以分解为它们的头部和尾部（您可以很容易地获得其中之一，但不能同时获得两者）这一事实使情况变得非常复杂因为到那时流已经 consumed - 听起来有人可以使用线性类型...）。

解决方案是保留一个可变变量。例如，该可变变量可以是测试一个数字是否是目前看到的任何其他数字的倍数的谓词。

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

   }
}

然后，你得到了预期的结果：

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

Answer 2

如果您接受 Scala 解决方案，这里是：

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 更惰性。在文档中，您甚至可以找到对应于 canonical Haskell zipWith implementation.

的斐波那契数列实现示例

Answer 3

可能是这样的解决方案？

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 4

编辑：筛子，未优化，return无限的素数流

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

初始Post:

一种更简单的解决方案，避免了一些不必要的操作（例如测试偶数）。

我们迭代从 3 到极限的所有奇数。

过滤函数内：

我们测试所有我们发现的比 sqrt(currentNumber) 向下舍入 smaller/equal 的素数。
如果他们除掉我们现在的人数 return false.
否则添加到找到的素数列表中 return 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 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
        );

Java 8：溪流和埃拉托色尼筛法

Java 8: streams and the Sieve of Eratosthenes

java

primes

haskell

sieve-of-eratosthenes

java-stream