我稍微修改了Sieve of Sundaram算法以减少不必要的迭代，它似乎非常快。
这个算法实际上比这个主题下最被接受的@Ted Hopp 的解决方案快两倍。解决 0 - 1M 之间的 78498 个素数在 Chrome 55 中需要 20~25 毫秒，在 FF 50.1 中需要 < 90 毫秒。另外@vitaly-t 的 get next prime 算法看起来很有趣，但结果也慢得多。
这是核心算法。人们可以应用分段和线程来获得极好的结果。
"use strict";
function primeSieve(n){
var a = Array(n = n/2),
t = (Math.sqrt(4+8*n)-2)/4,
u = 0,
r = [];
for(var i = 1; i <= t; i++){
u = (n-i)/(1+2*i);
for(var j = i; j <= u; j++) a[i + j + 2*i*j] = true;
}
for(var i = 0; i<= n; i++) !a[i] && r.push(i*2+1);
return r;
}
var primes = [];
console.time("primes");
primes = primeSieve(1000000);
console.timeEnd("primes");
console.log(primes.length);
循环限制解释：
就像 Erasthotenes 的筛选一样，Sundaram 的筛选算法也会从列表中划掉一些选定的整数。要选择要划掉哪些整数，规则是 i + j + 2ij ≤ n，其中 i 和 j 是两个索引，n 是总元素的数量。一旦我们划掉每一个 i + j + 2ij，剩下的数字就会被加倍和奇数化 (2n+1) 以显示素数列表。最后阶段实际上是偶数的自动折扣。它的证明在这里得到了很好的解释。
Sundaram 的筛选只有在正确选择循环索引开始和结束限制的情况下才会很快，这样就不会（或最少）消除非素数的冗余（多重）。由于我们需要 i 和 j 值来计算要划掉的数字，因此 i + j + 2ij 到 n 让我们看看如何处理。
i)所以我们必须找到 i 和 j 相等时可以取的最大值。即 2i + 2i^2 = n。我们可以使用二次公式轻松求解 i 的正值，即t = (Math.sqrt(4+8*n)-2)/4,
j)内循环索引 j 应该从 i 开始并运行到它可以与当前 i 值一致的点。仅此而已。由于我们知道 i + j + 2ij = n，这可以很容易地计算为u = (n-i)/(1+2*i);
虽然这不会完全消除冗余交叉，但它会“极大地”消除冗余。例如，对于 n = 50（检查最多 100 的素数）而不是 50 x 50 = 2500，我们总共将只进行 30 次迭代。很明显，这个算法不应该被视为 O(n^2) 时间复杂度的算法。
i j v
1 1 4
1 2 7
1 3 10
1 4 13
1 5 16
1 6 19
1 7 22 <<
1 8 25
1 9 28
1 10 31 <<
1 11 34
1 12 37 <<
1 13 40 <<
1 14 43
1 15 46
1 16 49 <<
2 2 12
2 3 17
2 4 22 << dupe #1
2 5 27
2 6 32
2 7 37 << dupe #2
2 8 42
2 9 47
3 3 24
3 4 31 << dupe #3
3 5 38
3 6 45
4 4 40 << dupe #4
4 5 49 << dupe #5
其中只有5个重复。22、31、37、40、49。对于 n = 100，冗余度约为 20%，但对于 n = 10M，它增加到 ~300%。这意味着 SoS 的进一步优化有可能随着 n 的增长更快地获得结果。因此，一个想法可能是分段并始终保持 n 小。
所以好吧..我决定更进一步地进行这个任务。
经过对重复交叉的一些仔细检查后，我意识到一个事实，除了i === 1情况，如果i或j指数值中的一个或两个在 4,7,10,13,16,19.. . 系列，生成重复的交叉。然后仅在 时才允许内循环转动i%3-1 !== 0，从而进一步减少了循环总数的 35-40%。因此，例如对于 1M 个整数，嵌套循环的总轮数从 1.4M 下降到 1M。哇..！我们在这里谈论的几乎是 O(n)。
我刚刚做了一个测试。在 JS 中，仅一个计数到 1B 的空循环就需要 4000 毫秒。在以下修改后的算法中，找到最多 100M 的素数需要相同的时间。
我还实现了这个算法的分割部分来推送给工作人员。这样我们也可以使用多个线程。但该代码稍后将遵循。
因此，让我向您介绍经过修改的 Sundaram 筛网可能在不分段时最好。它将使用 Chrome V8 和 Edge ChakraCore 在大约 15-20 毫秒内计算 0-1M 之间的素数。
"use strict";
function primeSieve(n){
var a = Array(n = n/2),
t = (Math.sqrt(4+8*n)-2)/4,
u = 0,
r = [];
for(var i = 1; i < (n-1)/3; i++) a[1+3*i] = true;
for(var i = 2; i <= t; i++){
u = (n-i)/(1+2*i);
if (i%3-1) for(var j = i; j < u; j++) a[i + j + 2*i*j] = true;
}
for(var i = 0; i< n; i++) !a[i] && r.push(i*2+1);
return r;
}
var primes = [];
console.time("primes");
primes = primeSieve(1000000);
console.timeEnd("primes");
console.log(primes.length);
嗯...最后我想我已经实现了一个筛子（它起源于 Sundaram 的巧妙 Sieve），这样它是我可以在互联网上找到的最快的 JavaScript 筛子，包括“Eratosthenes 的 Odds only Sieve”或“阿特金斯筛”。这也是为 web 工作者准备的，多线程。
这样想。在这台不起眼的单线程 AMD PC 中，JS 需要 3,300 毫秒才能计算到 10^9，而以下优化的分段 SoS 将仅在 14,000 毫秒内为我提供 50847534 个素数，达到 10^9。这意味着只是计数操作的 4.25 倍。我认为它令人印象深刻。
你可以自己测试一下；
console.time("tare");
for (var i = 0; i < 1000000000; i++);
console.timeEnd("tare");
在这里，我向您介绍最好的 Sundaram 分段 Seieve。
"use strict";
function findPrimes(n){
function primeSieve(g,o,r){
var t = (Math.sqrt(4+8*(g+o))-2)/4,
e = 0,
s = 0;
ar.fill(true);
if (o) {
for(var i = Math.ceil((o-1)/3); i < (g+o-1)/3; i++) ar[1+3*i-o] = false;
for(var i = 2; i < t; i++){
s = Math.ceil((o-i)/(1+2*i));
e = (g+o-i)/(1+2*i);
if (i%3-1) for(var j = s; j < e; j++) ar[i + j + 2*i*j-o] = false;
}
} else {
for(var i = 1; i < (g-1)/3; i++) ar[1+3*i] = false;
for(var i = 2; i < t; i++){
e = (g-i)/(1+2*i);
if (i%3-1) for(var j = i; j < e; j++) ar[i + j + 2*i*j] = false;
}
}
for(var i = 0; i < g; i++) ar[i] && r.push((i+o)*2+1);
return r;
}
var cs = n <= 1e6 ? 7500
: n <= 1e7 ? 60000
: 100000, // chunk size
cc = ~~(n/cs), // chunk count
xs = n % cs, // excess after last chunk
ar = Array(cs/2), // array used as map
result = [];
for(var i = 0; i < cc; i++) result = primeSieve(cs/2,i*cs/2,result);
result = xs ? primeSieve(xs/2,cc*cs/2,result) : result;
result[0] *=2;
return result;
}
var primes = [];
console.time("primes");
primes = findPrimes(1000000000);
console.timeEnd("primes");
console.log(primes.length);
我不确定它是否会比这更好。我很想听听你的意见。