具有启动逻辑的延迟筛选算法
Postponed Sieve algorithm with start logic
基于the answer by 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. All main algorithms can be found in src/sieve.ts.
分享我使用的最终代码
我修改了 Will Ness 的精彩回答
允许打印任何起始值。如下所述，我认为没有办法避免它必须计算所有较早的素数，如果你想要一个更高素数的无限序列。
调整了变量名称以帮助理解算法。
将映射中存储的内容从质因数的 2 倍更改为仅质因数，以使 reader 更容易遵循算法。
将一部分代码移到一个子函数中，同样是为了便于 reader 理解。
更改了算法中间3路选择的控制流程，并添加了注释，简化了理解。它可能稍微慢一点，因为它不再首先测试最常见的真实条件，但是 readers.
更容易
function* primeGenerator() {
yield 2;
yield 3;
yield 5;
yield 7;
const multiplesWithAFactor = new Map();
// We only need to consider potential factors that are themselves prime
// Start with 3 and get further prime factors on demand from a child instance of ourself.
let biggestFactorConsidered = 3;
const childStreamOfPrimes = primeGenerator();
childStreamOfPrimes.next(); // Discard the 2
childStreamOfPrimes.next(); // Discard the 3
let candidate = 7; // We have already yielded 7 as a prime above, so on the first iteration of the while loop we will be testing 9.
while (true) {
candidate += 2;
// Assess candidate, into one of three outcomes: square, non-square multiple, prime. This order is arranged for ease of understanding, but for maximum speed efficiency you should test in the order in Will Ness's version.
const factorOfCandidate = multiplesWithAFactor.get(candidate);
if (candidate === biggestFactorConsidered * biggestFactorConsidered) {
// A square, so from now on we will need to consider the next factor, too.
markNextUnmarkedMultiple(candidate, biggestFactorConsidered);
biggestFactorConsidered = childStreamOfPrimes.next().value;
} else if (factorOfCandidate) {
// A non-square multiple. Can forget that fact now, and instead mark the next unmarked multiple of the same prime factor
multiplesWithAFactor.delete(candidate);
markNextUnmarkedMultiple(candidate, factorOfCandidate);
} else {
// Prime
yield candidate;
}
}
// This is a subfunction for ease of understanding, but for maximum efficiency you should put this in the while loop above, and have the "yield candidate" avoid calling it, via a "continue" statement.
function markNextUnmarkedMultiple(candidate, factor) {
let nextMultiple = candidate + 2 * factor;
while (multiplesWithAFactor.has(nextMultiple)) {
nextMultiple += 2 * factor;
}
multiplesWithAFactor.set(nextMultiple, factor);
}
}
const maxItems = 20;
const minimumPrintablePrime = 5e8;
console.log("Running");
const primeObject = primeGenerator();
let count = 0;
do {
const prime = primeObject.next().value;
if (prime > minimumPrintablePrime) { // If you don't like seeing this process of reading non-printed primes out here in the parent code, you can do it within the primeGenerator itself. Either way, _someone_ has to call the prime generator for all primes up to the square root of the starting value.
console.log(prime);
count++;
}
} while (count < maxItems);
该算法在存储方面非常经济
它使用了素数生成器的多个实例。你称之为“主要”，它沿着检查候选人的方向运行，同时存储一组它知道是较小素因子的倍数的未来候选人。
在任何时候，当考虑候选 N 时，其存储的映射包含一个条目 for 每个质因数直到 sqrt(N) 但存储在下一个映射中算法将达到的主要因素的倍数，因为它从当前候选人向前探索。
只要候选人出现在这个倍数图中，它就可以拒绝该候选人。该地图告诉我们，对于那个倍数，告诉我们这个数字是倍数的主要因素是什么。比如15被标记为3的倍数，当算法到了15的时候，意识到是3的倍数，就拒绝了15。
从现在开始，不再需要记住 15 是倍数，因为在此算法实例中，15 将永远不会再次成为候选者。它可以从它的倍数映射中删除 15 条目，并将其替换为下一个 3 的倍数。但是下一个倍数将 始终 是偶数，因为所有候选者（例如 15）和所有因素（例如 3）都是奇数。因此它只需要告诉地图 15 + 2x3 是一个倍数，即它可以向前移动 2 x 倍数。此外，如果结果数字 21 已经被标记为倍数，则不需要标记该数字：它可以进一步前进 2x3 到 15 + 2x3 + 2x3，等等，直到找到一个尚未标记为的数字一个倍数。
巧妙地，这个过程确保每个因素（例如 3）永远在地图中标记倍数。为了评估候选 N，地图将只包含一个条目，每个素数最多为 sqrt(N)。
当候选人上升到目前考虑的最大因素的平方以上时，算法需要得到下一个因素。它只是使用自身的第二个实例来获取序列中的下一个素数。起初我担心这会产生巨大的内存需求，但事实并非如此。评估一个数字 ~2^64，将需要 ~2^32 的所有第二个实例，这又会调用 ~2^16 的第三个实例，依此类推。即使对于巨大的素数，也只需要创建少数几个生成器实例，如果一个实例的映射具有高达 F 的因子，则下一个实例只需要高达 sqrt(F) 的因子，它会迅速变小。
即使是 Ness 算法仍然需要构建一个包含直到 sqrt(N) 的所有因子的映射
它需要地图包含所有这些因素，以便它可以正确地拒绝 N 附近的候选人。
但它也_最终_需要 sqrt(N) 和 N 之间的因数
因为只有这样才能确信N到N^2的数是素数。
我的结论
我认为它需要迭代才能工作。我看不到在任意候选人身上启动它的方法，例如10^8，没有预先用（所有）素数填充地图，最多 10^4。
最有效的预填充方法是 运行 算法本身，如果您简单地要求它产生（但不打印）所有素数，实际上它就是这样做的最多 10^8.
我怀疑该算法 如此 高效，这是使其进入适当位置以从任意候选开始的最佳方法，例如1e8，是靠运行算法本身，即没有捷径。情况了不起！
这似乎在 Will 的更新答案中得到了证实，其中算法调用自身来预填充筛子。在预填充结束时，筛子包含每个素数的一个条目，直到 sqrt(start)。我的版本要慢得多，但这并不是因为它收集的素数比 Will 的多；这是因为它 (a) 以不同的顺序测试 3 个条件（以便人们更容易遵循）和 (b) 将一些代码提取到子函数中（再次使其更易于理解）。显然 Will 的方法更适合生产代码！
（更新：在此答案底部添加了有效的 JS 代码）。
这是埃拉托色尼的筛法：
<em>素数</em> = {<em>2</em>,<em>3</em>,... } \ ⋃<sub>(<em>p</em> ← <em>素数</em>)</sub> {<em>p</em> <sup>2</sup>, <em>p</em><sup>2</sup>+<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><sup> 2</sup>, <em>p</em><sup>2</sup>+2<em>p</em>, ...}
其中 \ 是集差（读作“减”），∪ 集并集，⋃ 集的大并集。
举例说明：
{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 是下一个素数在 qs.
之后
每一个倍数都是最小的不小于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 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（五次）调用的惊人递归深度实现的。
重复平方的力量！或其逆操作，log log 操作：
log<sub>2</sub>( log<sub>2</sub>( 500000000 )) == 4.85
基于the answer by 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. All main algorithms can be found in src/sieve.ts.
分享我使用的最终代码我修改了 Will Ness 的精彩回答
允许打印任何起始值。如下所述，我认为没有办法避免它必须计算所有较早的素数，如果你想要一个更高素数的无限序列。
调整了变量名称以帮助理解算法。
将映射中存储的内容从质因数的 2 倍更改为仅质因数，以使 reader 更容易遵循算法。
将一部分代码移到一个子函数中，同样是为了便于 reader 理解。
更改了算法中间3路选择的控制流程，并添加了注释，简化了理解。它可能稍微慢一点，因为它不再首先测试最常见的真实条件，但是 readers.
更容易
function* primeGenerator() {
yield 2;
yield 3;
yield 5;
yield 7;
const multiplesWithAFactor = new Map();
// We only need to consider potential factors that are themselves prime
// Start with 3 and get further prime factors on demand from a child instance of ourself.
let biggestFactorConsidered = 3;
const childStreamOfPrimes = primeGenerator();
childStreamOfPrimes.next(); // Discard the 2
childStreamOfPrimes.next(); // Discard the 3
let candidate = 7; // We have already yielded 7 as a prime above, so on the first iteration of the while loop we will be testing 9.
while (true) {
candidate += 2;
// Assess candidate, into one of three outcomes: square, non-square multiple, prime. This order is arranged for ease of understanding, but for maximum speed efficiency you should test in the order in Will Ness's version.
const factorOfCandidate = multiplesWithAFactor.get(candidate);
if (candidate === biggestFactorConsidered * biggestFactorConsidered) {
// A square, so from now on we will need to consider the next factor, too.
markNextUnmarkedMultiple(candidate, biggestFactorConsidered);
biggestFactorConsidered = childStreamOfPrimes.next().value;
} else if (factorOfCandidate) {
// A non-square multiple. Can forget that fact now, and instead mark the next unmarked multiple of the same prime factor
multiplesWithAFactor.delete(candidate);
markNextUnmarkedMultiple(candidate, factorOfCandidate);
} else {
// Prime
yield candidate;
}
}
// This is a subfunction for ease of understanding, but for maximum efficiency you should put this in the while loop above, and have the "yield candidate" avoid calling it, via a "continue" statement.
function markNextUnmarkedMultiple(candidate, factor) {
let nextMultiple = candidate + 2 * factor;
while (multiplesWithAFactor.has(nextMultiple)) {
nextMultiple += 2 * factor;
}
multiplesWithAFactor.set(nextMultiple, factor);
}
}
const maxItems = 20;
const minimumPrintablePrime = 5e8;
console.log("Running");
const primeObject = primeGenerator();
let count = 0;
do {
const prime = primeObject.next().value;
if (prime > minimumPrintablePrime) { // If you don't like seeing this process of reading non-printed primes out here in the parent code, you can do it within the primeGenerator itself. Either way, _someone_ has to call the prime generator for all primes up to the square root of the starting value.
console.log(prime);
count++;
}
} while (count < maxItems);
该算法在存储方面非常经济
它使用了素数生成器的多个实例。你称之为“主要”，它沿着检查候选人的方向运行，同时存储一组它知道是较小素因子的倍数的未来候选人。
在任何时候，当考虑候选 N 时，其存储的映射包含一个条目 for 每个质因数直到 sqrt(N) 但存储在下一个映射中算法将达到的主要因素的倍数，因为它从当前候选人向前探索。
只要候选人出现在这个倍数图中，它就可以拒绝该候选人。该地图告诉我们，对于那个倍数，告诉我们这个数字是倍数的主要因素是什么。比如15被标记为3的倍数，当算法到了15的时候，意识到是3的倍数，就拒绝了15。
从现在开始，不再需要记住 15 是倍数，因为在此算法实例中，15 将永远不会再次成为候选者。它可以从它的倍数映射中删除 15 条目，并将其替换为下一个 3 的倍数。但是下一个倍数将 始终 是偶数，因为所有候选者（例如 15）和所有因素（例如 3）都是奇数。因此它只需要告诉地图 15 + 2x3 是一个倍数，即它可以向前移动 2 x 倍数。此外，如果结果数字 21 已经被标记为倍数，则不需要标记该数字：它可以进一步前进 2x3 到 15 + 2x3 + 2x3，等等，直到找到一个尚未标记为的数字一个倍数。
巧妙地，这个过程确保每个因素（例如 3）永远在地图中标记倍数。为了评估候选 N，地图将只包含一个条目，每个素数最多为 sqrt(N)。
当候选人上升到目前考虑的最大因素的平方以上时，算法需要得到下一个因素。它只是使用自身的第二个实例来获取序列中的下一个素数。起初我担心这会产生巨大的内存需求，但事实并非如此。评估一个数字 ~2^64，将需要 ~2^32 的所有第二个实例，这又会调用 ~2^16 的第三个实例，依此类推。即使对于巨大的素数，也只需要创建少数几个生成器实例，如果一个实例的映射具有高达 F 的因子，则下一个实例只需要高达 sqrt(F) 的因子，它会迅速变小。
即使是 Ness 算法仍然需要构建一个包含直到 sqrt(N) 的所有因子的映射
它需要地图包含所有这些因素，以便它可以正确地拒绝 N 附近的候选人。
但它也_最终_需要 sqrt(N) 和 N 之间的因数
因为只有这样才能确信N到N^2的数是素数。
我的结论
我认为它需要迭代才能工作。我看不到在任意候选人身上启动它的方法，例如10^8，没有预先用（所有）素数填充地图，最多 10^4。
最有效的预填充方法是 运行 算法本身，如果您简单地要求它产生（但不打印）所有素数，实际上它就是这样做的最多 10^8.
我怀疑该算法 如此 高效，这是使其进入适当位置以从任意候选开始的最佳方法，例如1e8，是靠运行算法本身，即没有捷径。情况了不起！
这似乎在 Will 的更新答案中得到了证实，其中算法调用自身来预填充筛子。在预填充结束时，筛子包含每个素数的一个条目，直到 sqrt(start)。我的版本要慢得多，但这并不是因为它收集的素数比 Will 的多；这是因为它 (a) 以不同的顺序测试 3 个条件（以便人们更容易遵循）和 (b) 将一些代码提取到子函数中（再次使其更易于理解）。显然 Will 的方法更适合生产代码！
（更新：在此答案底部添加了有效的 JS 代码）。
这是埃拉托色尼的筛法：
<em>素数</em> = {<em>2</em>,<em>3</em>,... } \ ⋃<sub>(<em>p</em> ← <em>素数</em>)</sub> {<em>p</em> <sup>2</sup>, <em>p</em><sup>2</sup>+<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><sup> 2</sup>, <em>p</em><sup>2</sup>+2<em>p</em>, ...}
其中 \ 是集差（读作“减”），∪ 集并集，⋃ 集的大并集。
举例说明：
{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 是下一个素数在 qs.
每一个倍数都是最小的不小于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 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（五次）调用的惊人递归深度实现的。
重复平方的力量！或其逆操作，log log 操作：
log<sub>2</sub>( log<sub>2</sub>( 500000000 )) == 4.85