问题描述
根据 Will Ness 的回答，我一直在使用 JavaScript 改编版来适应延迟筛分算法:
Based on the answer by Will Ness, I've been using a JavaScript adaptation for the postponed sieve algorithm:
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 点，我正在努力解决它，因为这里的逻辑并不简单.
But now that I need to add start point to it, I am struggling to wrap my head around it, for the logic here isn't straightforward.
当 start 是素数时，我需要它作为第一个值.当 start 不是素数时，我需要序列从 start 之后的第一个素数开始.
When start is a prime, I need it to be the first value. And when start is not a prime, I need the sequence to start with the first prime after start.
Will Ness 在其中一条评论中建议:
Will Ness suggested in one of the comments:
您必须为起点提供有效的筛选字典.很容易得到所需的质数 - 只需将这个算法运行到 sqrt(start)，然后你需要找到每个核心质数的倍数就在开始的上方(或者是正下方?)，同时注意重复.
然而，将其变为现实并不是那么简单(或者至少对我而言):|
Wielding this into reality however is not that simple (or at least for me) :|
任何人都可以帮助更新这种 *primes(start) 实现的算法(最好是在上面的 JavaScript 中)?
Can anybody help with updating this algorithm for such *primes(start) implementation (preferably in JavaScript as above)?
function * primes(start) {
// how to amend it to support 'start' logic???
}
结论
根据 Will Ness 的出色回答，我决定通过公共图书馆分享我使用的最终代码 - 素数生成器.所有主要算法都可以在 src/sieve.ts 中找到.
Conclusion
Following the excellent answer by Will Ness, I decided to share the final code I used, through a public library - primes-generator. All main algorithms can be found in src/sieve.ts.
推荐答案
(更新:在此答案底部添加了有效的 JS 代码).
这是埃拉托色尼的筛子:
This is the sieve of Eratosthenes:
primes = {2,3,...} \ U {p, p+p, ...} = {2} +oddPrimes ,oddPrimes = {3,5,...} \ U {p, p+2*p, ...}
primes = {2,3,...} \ U {p, p+p, ...} = {2} + oddPrimes , oddPrimes = {3,5,...} \ U {p, p+2*p, ...}
其中 \ 是集合差(读作减")，而 U 是集合的大并集.
where \ is set difference (read "minus"), and U big union of sets.
一个例子可以说明:
{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 都以某种状态存在，循环中的其余变量也是如此.所以我们只需要直接重新创建这个状态即可.
The code you refer to in the question implements this approach. At any point in time, when considering a certain candidate, sieve exists in a certain state, as are the rest of the variables in the loop. So we just need to re-create this state directly.
假设我们正在考虑将 i = 19 作为当前候选对象.那时我们有 sieve = { (21, 6) } 和 p = 5.
Let's say we're considering i = 19 as the current candidate. At that point we have sieve = { (21, 6) } and p = 5.
这意味着对于候选 i，sieve 包含所有素数 q 的倍数，使得 q^2 ，p 是 qs 之后的下一个质数.
This means for a candidate i, sieve contains multiples of all the primes q such that q^2 < i, and p is the next prime after the qs.
每个倍数都是不小于i的最小的一个，筛子里没有重复的.然后它处于一致状态，可以从那时起继续.
Each of the multiples is the smallest one not smaller than i, and there are no duplicates in the sieve. Then it's in a consistent state and can be continued from that point on.
因此，在伪代码中:
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
然后做和之前一样的循环.
and then do the same loop as before.
根据要求，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);
}
}
正确产生第一个10 很快就超过了 500,000,000on ideone:>
Correctly produces the first 10 primes above 500,000,000 in no time at all on ideone:
Success #stdin #stdout 0.03s 17484KB
500000003,500000009,500000041,500000057,500000069,
500000071,500000077,500000089,500000093,500000099
显然，它具有 5(五)次调用的惊人递归深度.
Apparently it does so with the whopping recursion depth of 5 (five) invocations.
重复平方的威力！(或者它的反面，log log 操作:) log( log( 500000000 )) == 4.85
The power of the repeated squaring! (or its inverse, the log log operation:) log( log( 500000000 )) == 4.85
这篇关于具有启动逻辑的延迟筛分算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！