javascript - 具有启动逻辑的延迟筛选算法

Question

基于 this Python answer通过 Will Ness ，我一直在为那个答案中的延迟筛选算法使用 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 之后的第一个素数开始。

Will Ness 在其中一条评论中建议:

You would have to come up with the valid sieve dictionary for the start point. It's easy to get the needed primes - just run this algo up to sqrt(start), then you need to find each core prime's multiple just above (or is it just below?) the start, while minding the duplicates.

然而，将其变为现实并不是那么简单(至少对我而言):|

任何人都可以帮助更新这个算法以实现这样的 *primes(start) 实现(最好是在上面的 JavaScript 中)？

function * primes(start) {

  // how to amend it to support 'start' logic???

}

结论

根据 Will Ness 的出色回答，我决定通过公共(public)图书馆分享我使用的最终代码 - primes-generator .所有主要算法都可以在src/sieve.ts中找到.

Answer 1

(更新:在此答案的底部添加了有效的 JS 代码)。

这是埃拉托色尼筛法:

<em>primes</em> = {<em>2</em>,<em>3</em>,...} \ ⋃<sub>(<em>p</em> ← <em>primes</em>)</sub> {<em>p</em>², <em>p</em>²+<em>p</em>, ...}
<code> = {<em>2</em>} ∪ <em>oddPrimes</em> ,
<code> <em>oddPrimes</em> = {<em>3</em>,<em>5</em>,...} \ ⋃<sub>(<em>p</em> ← <em>oddPrimes</em>)</sub> {<em>p</em>², <em>p</em>²+2<em>p</em>, ...}</code></code>

哪里\是设定差(读作“减”)，∪设置联合，和⋃集合的大联合。

一个例子可以说明:

{2,3,4,5,6,7,8,9,10,11,12,13,14,15,...}
 \             |
   { 4,  6,  8,| 10,   12,   14,   16,   18, ...}
    \          .
             { 9,      12,      15,      18,    21,  ...}
       \ 
                                               { 25, 30, 35, ...}
          \                                     { 49, 56, 63, ...}
            \                                     { 121, 132, 143, ...}
              \  ........

或者对于奇素数，

{3,5,7,9,11,13,15,17,19,21,23,25,27,29,31, ...}
 \                    |
     { 9,      15,    | 21,      27,      33, ...}
   \                          .
                            { 25,            35, ...}
     \                                        { 49, 63, ...}
      \                                         { 121, 143, ...}
       \  ........

您在问题中引用的代码实现了这种方法。在任何时候，当考虑某个候选人时，sieve存在于特定状态，循环中的其余变量也是如此。所以我们只需要直接重新创建这个状态即可。

假设我们正在考虑 i = 19作为现任候选人。那时我们有sieve = { (21, 6) }和 p = 5 .

这意味着候选人 i , sieve包含所有素数的倍数 q这样 q^2 < i , 和 p是 q 之后的下一个素数

每一个倍数都是不小于i的最小倍数, 并且筛子中没有重复项。然后它处于一致状态，可以从那时起继续。

因此，在伪代码中:

primes() = ..... // as before

primesFrom(start) =
  let
  { primes.next()
  ; ps = takeWhile( (p => p^2 < start) , primes() )
  ; p = primes.next_value()
  ; mults = map( (p => let 
                       { s = 2*p 
                       ; n = (start-p)/s  // integer division NB!
                       ; r = (start-p)%s
                       ; m = p + (r>0 ? n+1 : n)*s
                       }
                       ( m, s) )
                , ps)
  }
  for each (m,s) in mults
    if m in sieve
       increment m by s until m is not in sieve
    add (m,s) to sieve

然后像以前一样做同样的循环。

---

根据要求，JS代码:

function *primesFrom(start) {
    if (start <= 2) { yield 2; }
    if (start <= 3) { yield 3; }
    if (start <= 5) { yield 5; }
    if (start <= 7) { yield 7; }
    const sieve = new Map();
    const ps = primesFrom(2);
    ps.next();                 // skip the 2
    let p = ps.next().value;   // p==3
    let psqr = p * p;          // p^2, 9
    let c = psqr;              // first candidate, 9
    let s = 6;                 // step value
    let m = 9;                 // multiple

    while( psqr < start )      // must adjust initial state
    {
         s = 2 * p;            
         m = p + s * Math. ceil( (start-p)/s );  // multiple of p
         while (sieve.has(m)) m += s;
         sieve.set(m, s);
         p = ps.next().value;
         psqr = p * p;
    }
    if ( start > c) { c = start; }
    if ( c%2 === 0 ) { c += 1; }
    
    for ( ;  true ;  c += 2 )     // main loop
    {
        s = sieve.get(c);
        if (s !== undefined) {
            sieve.delete(c);      // c composite
        } else if (c < psqr) {
            yield c;              // c prime
            continue;
        } else {                  // c == p^2
            s = 2 * p;
            p = ps.next().value;
            psqr = p * p;
        }
        m = c + s;
        while (sieve.has(m)) m += s;
        sieve.set(m, s);
    }
}

Correctly立即产生 10 个大于 500,000,000 的素数 on ideone :

Success #stdin #stdout 0.03s 17484KB
500000003,500000009,500000041,500000057,500000069,
500000071,500000077,500000089,500000093,500000099

显然，它是通过 5(五次)调用的惊人递归深度实现的。

重复平方的力量!或者它的倒数，log log操作:

log<sub>2</sub>( log<sub>2</sub>( 500000000 )) == 4.85