如何为JavaScript版Postponed Sieve延迟筛法添加start起始参数

问题描述 #

我此前基于延迟筛法（Postponed Sieve）的Python实现，适配出了如下JavaScript版本的素数生成器：

function * primes() {
    yield 2;
    yield 3;
    yield 5;
    yield 7;
    const sieve = new Map();
    const ps = primes();
    ps.next() && ps.next();
    for (let p = 3, i = 9; true; i += 2) {
        let s = sieve.get(i);
        if (s !== undefined) {
            sieve.delete(i);
        } else if (i < p * p) {
            yield i;
            continue;
        } else {
            s = 2 * p;
            p = ps.next().value;
        }
        let k = i + s;
        while (sieve.has(k)) k += s;
        sieve.set(k, s);
    }
}

现在需要为该生成器添加start参数，逻辑要求如下：

• 若start本身是素数，序列第一个输出值为start
• 若start不是素数，序列从start之后的第一个素数开始输出

已知实现思路为：为起始点构造有效的筛表，先运行算法生成所有小于等于sqrt(start)的素数，再找到每个核心素数刚好大于start的倍数，同时处理重复值。求符合要求的JavaScript实现。

实现方案 #

function* primes(start = 2) {
    // 边界处理：起始值小于2时直接从2开始
    if (start <= 2) {
        yield 2;
    }
    // 调整起始奇数：确保从大于等于start的第一个奇数开始遍历
    let current = start % 2 === 0 ? start + 1 : start;
    if (current < 3) current = 3;

    const sieve = new Map();
    const ps = primes();
    // 先跳过2，取第一个奇素数3
    ps.next();
    let p = ps.next().value;
    const sqrtStart = Math.ceil(Math.sqrt(start));

    // 预生成所有<=sqrt(start)的素数，初始化筛表
    while (p <= sqrtStart) {
        // 计算p的第一个>=current的奇数倍数
        let multiple = Math.ceil(current / p) * p;
        if (multiple % 2 === 0) multiple += p;
        // 避免重复键，步进2p（跳过偶数倍数）
        while (sieve.has(multiple)) multiple += 2 * p;
        sieve.set(multiple, 2 * p);
        p = ps.next().value;
    }

    // 遍历奇数，执行筛法逻辑
    for (let i = current; true; i += 2) {
        let s = sieve.get(i);
        if (s !== undefined) {
            sieve.delete(i);
        } else if (i < p * p) {
            yield i;
            continue;
        } else {
            s = 2 * p;
            p = ps.next().value;
        }
        let k = i + s;
        while (sieve.has(k)) k += s;
        sieve.set(k, s);
    }
}

用法示例

// 输出从10开始的素数：11,13,17,19,23...
const gen = primes(10);
console.log(gen.next().value); // 11
console.log(gen.next().value); // 13

后续说明 #

最终提问者参考思路完成了完整实现，开源为公共素数生成器库，核心逻辑可查看库中的src/sieve.ts文件。

内容的提问来源于stack exchange，提问作者vitaly-t