JavaScript高阶生成器实现埃氏筛法生成素数

高阶生成器原理与素数生成示例

生成器是JavaScript中用于控制迭代流程的重要特性，但高阶生成器的概念相对少见。本文将深入探讨其工作原理及应用场景。

首先通过具体代码示例进行演示：

function* numFrom(start: number) {
    while (true) yield start++
}

function* filter(nums: Generator<number>, prime: number) {
    for (const n of nums) if (n % prime !== 0) yield n
}

let cur = numFrom(2)

for (let i = 0; i < 10; i++) {
    const prime = cur.next()
    if (!prime.done) {
        console.log(i, ':', prime.value)
        cur = filter(cur, prime.value)
    }
}

运行上述代码后，控制台输出结果如下：

0 : 2 1 : 3 2 : 5 3 : 7 4 : 11 5 : 13 6 : 17 7 : 19 8 : 23 9 : 29

其中函数 filter 接收一个生成器作为参数，并返回一个新的生成器实例，这种模式被称为高阶生成器。

function* filter(nums: Generator<number>, prime: number) {
    for (const n of nums) if (n % prime !== 0) yield n
}

该函数的核心功能是过滤掉由 nums: Generator<number> 产生的数值中，能够被 prime 整除的合数：

const gen = filter(numFrom(10), 3)
for (let i = 0; i < 10; i++) {
    const n = gen.next()
    if (!n.done) console.log(n.value)
}

该过滤器的运行结果如下：

10 11 13 14 16 17 19 20 22 23

观察输出可知，3 的倍数，包括 12、15、18 以及 21 等数值，均已被成功过滤剔除。

若将该函数的返回值再次作为参数传入 filter，即可实现多层过滤，从而剔除更多合数：

let gen = filter(numFrom(10), 3) // 从 10 开始，不能被 3 整除的数
gen = filter(gen, 5) // 从 10 开始，不能被 3 和 5 整除的数
...

通过持续将当前生成器与已生成的素数传入处理流程，即可实现类似埃氏筛法的素数生成机制。

let cur = numFrom(2)

for (let i = 0; i < 10; i++) {
    const prime = cur.next()
    if (!prime.done) {
        console.log(i, ':', prime.value)
        cur = filter(cur, prime.value) // 产生新的生成器
    }
}

numFrom(2) -> filter(2) -> filter(3) -> filter(5) -> filter(7) ...

若对执行逻辑尚存疑问，可通过在控制台打印详细日志来观察内部过程：

function* numFrom(start: number) {
    while (true) {
        console.log('\nnum yield', start)
        yield start++
    }
}

let filterDeep = 0
function* filter(nums: Generator<number>, prime: number) {
    const deep = filterDeep++
    for (const n of nums)
        if (n % prime !== 0) {
            console.log(`filter yield[${deep}] ${n}`)
            yield n
        } else console.log(`filtered[${deep}] ${n} by ${prime}`)
}

let cur = numFrom(2)

for (let i = 0; i < 10; i++) {
    const prime = cur.next()
    if (!prime.done) {
        console.log(i, ':', prime.value)
        cur = filter(cur, prime.value)
    }
}

详细的控制台输出日志如下：

num yield 2 0 : 2 num yield 3 filter yield[0] 3 1 : 3 num yield 4 filtered[0] 4 by 2 num yield 5 filter yield[0] 5 filter yield[1] 5 2 : 5 num yield 6 filtered[0] 6 by 2 num yield 7 filter yield[0] 7 filter yield[1] 7 filter yield[2] 7 3 : 7 num yield 8 filtered[0] 8 by 2 num yield 9 filter yield[0] 9 filtered[1] 9 by 3 num yield 10 filtered[0] 10 by 2 num yield 11 filter yield[0] 11 filter yield[1] 11 filter yield[2] 11 filter yield[3] 11 4 : 11 num yield 12 filtered[0] 12 by 2 num yield 13 filter yield[0] 13 filter yield[1] 13 filter yield[2] 13 filter yield[3] 13 filter yield[4] 13 5 : 13 num yield 14 filtered[0] 14 by 2 num yield 15 filter yield[0] 15 filtered[1] 15 by 3 num yield 16 filtered[0] 16 by 2 num yield 17 filter yield[0] 17 filter yield[1] 17 filter yield[2] 17 filter yield[3] 17 filter yield[4] 17 filter yield[5] 17 6 : 17 num yield 18 filtered[0] 18 by 2 num yield 19 filter yield[0] 19 filter yield[1] 19 filter yield[2] 19 filter yield[3] 19 filter yield[4] 19 filter yield[5] 19 filter yield[6] 19 7 : 19 num yield 20 filtered[0] 20 by 2 num yield 21 filter yield[0] 21 filtered[1] 21 by 3 num yield 22 filtered[0] 22 by 2 num yield 23 filter yield[0] 23 filter yield[1] 23 filter yield[2] 23 filter yield[3] 23 filter yield[4] 23 filter yield[5] 23 filter yield[6] 23 filter yield[7] 23 8 : 23 num yield 24 filtered[0] 24 by 2 num yield 25 filter yield[0] 25 filter yield[1] 25 filtered[2] 25 by 5 num yield 26 filtered[0] 26 by 2 num yield 27 filter yield[0] 27 filtered[1] 27 by 3 num yield 28 filtered[0] 28 by 2 num yield 29 filter yield[0] 29 filter yield[1] 29 filter yield[2] 29 filter yield[3] 29 filter yield[4] 29 filter yield[5] 29 filter yield[6] 29 filter yield[7] 29 filter yield[8] 29 9 : 29

参考资料：

通道 - Kotlin 官方文档 https://book.kotlincn.net/text/channels.html

以上即为JavaScript利用高阶生成器进行过滤以生成素数的完整解析，更多相关技术细节欢迎查阅本站其他文章。