这个在Kotlin中使用generateSequence的素数生成函数不太好理解。 :(

Question

val primes = generateSequence(2 to generateSequence(3) {it + 2}) {
  val currSeq = it.second.iterator()
  val nextPrime = currSeq.next()
  nextPrime to currSeq.asSequence().filter { it % nextPrime != 0}
}.map {it.first}
println(primes.take(10).toList()) // prints [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

我试图了解这个函数的工作原理，但对我来说并不容易。有人可以解释它是如何工作的吗？谢谢

Answer 1

它使用“Eratosthenes 筛法”生成无限的素数序列（参见此处：https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes）。

此实现使用一对序列来执行此操作。每对的第一个元素是当前素数，第二个元素是大于该素数且不能被任何先前素数整除的整数序列。

它以 2 to [3, 5, 7, 9, 11, 13, 15, 17, ...] 对开头，由 2 to generateSequence(3) { it + 2 } 给出。使用这一对，我们通过获取序列的第一个元素（现在是 3）然后从序列中移除所有可被 3 整除的数字（移除 9、15、21 等）来创建序列的下一对。这给了我们这对：3 to [5, 7, 11, 13, 17, ...]。重复这个模式会给我们所有的素数。

在创建了这样的对序列之后，我们最终.map { it.first }只选择实际的素数，而不是内部序列。

对的序列将像这样演变：

2 to [3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, ...]
3 to [5, 7, 11, 13, 17, 19, 23, 25, 29, ...]
5 to [7, 11, 13, 17, 19, 23, 29, ...]
7 to [11, 13, 17, 19, 23, 29, ...]
11 to [13, 17, 19, 23, 29, ...]
13 to [17, 19, 23, 29, ...]
// and so on

这个在Kotlin中使用generateSequence的素数生成函数不太好理解。 :(

This prime generating function using generateSequence in Kotlin is not easy to understand. :(

kotlin

sequence

primes

lazy-sequences