我稍微修改了Sundaram算法的 Sieve 以减少不必要的迭代，它似乎非常快。
这个算法实际上比这个主题下最被接受的@Ted Hopp 的解决方案快两倍。解决 0 - 1M 之间的 78498 个素数在 Chrome 55 中需要 20~25 毫秒，在 FF 50.1 中需要 < 90 毫秒。@ vitaly -t 的获取下一个素数算法看起来很有趣，但结果也慢得多。
这是核心算法。可以应用分段和线程来获得极好的结果。
"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 小。
所以好吧..我决定把这个任务更进一步。
经过对反复交叉的一些仔细检查后，我意识到，除案例外，如果or索引值中i === 1的一个或两个在 4、7、10、13、16、19 之间。 .series，生成一个重复的交叉。然后只在 时允许内循环转动，从而实现循环总数进一步减少 35-40%。因此，例如对于 1M 整数，嵌套循环的总转数从 1.4M 下降到 1M。哇..！我们在这里谈论的几乎是 O(n)。iji%3-1 !== 0
我刚刚做了一个测试。在 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 的巧妙筛子），它是我可以在互联网上找到的最快的 JavaScript 筛子，包括“Eratosthenes 的 Odds only Sieve”或“阿特金斯筛”。这也为网络工作者、多线程做好了准备。
这样想。在这台用于单线程的简陋 AMD PC 中，JS 需要 3,300 毫秒才能计数到 10^9，以下优化的分段 SoS 将在 14,000 毫秒内为我提供高达 10^9 的 50847534 个素数。这意味着只是计数的 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);
我不确定它是否比这更好。我很想听听你的意见。