我一直在玩 Haskell，发现它很吸引人，尤其是惰性求值特性，它允许我们处理（可能）无限列表。
由此推导出埃拉托色尼筛法的漂亮实现以获得无限素数列表：
primes = sieve [2..]
where
sieve (x:xs) = x : sieve [i | i <- xs, i `mod` x /= 0]
仍在使用 Haskell，我可以有：
takeWhile (<1000) primes
这给了我直到 1000 (
ntake 1000 primes
这给了我前 1000 个素数
我试图用 Javascript 实现它，忘记了“无限”的可能性，这就是我想出的：
const sieve = list => {
if (list.length === 0) return []
const first = list.shift()
const filtered = list.filter(x => x % first !== 0)
return [first, ...sieve(filtered)]
}
const getPrimes = n => {
const list = new Array(n - 1).fill(null).map((x, i) => i + 2)
return sieve(list)
}
它完美地工作（如果我没有首先达到最大调用堆栈大小），但我只能得到质数“直到”
n我怎么能用它来实现一个函数，而不是返回“前 n”个素数？
我已经尝试了很多方法，但无法让它发挥作用。
奖金
有什么方法可以使用尾调用优化或其他方法来避免大型
N正如@VLAZ 所建议的，我们可以使用生成器来做到这一点：
function* removeMultiplesOf(x, iterator) {
for (const i of iterator)
if (i % x != 0)
yield i;
}
function* eratosthenes(iterator) {
const x = iterator.next().value;
yield x;
yield* eratosthenes(removeMultiplesOf(x, iterator));
}
function* from(i) {
while (true)
yield i++;
}
function* take(n, iterator) {
if (n <= 0) return;
for (const x of iterator) {
yield x;
if (--n == 0) break;
}
}
const primes = eratosthenes(from(2));
console.log(Array.from(take(1000, primes)));顺便说一句，我认为可以通过不重复除法来优化它：
function* removeMultiplesOf(x, iterator) {
let n = x;
for (const i of iterator) {
while (n < i)
n += x;
if (n != i)
yield i;
}
}
但快速基准测试表明它实际上与简单函数一样快。
好吧，在为此工作了整个周末之后，我想我找到了我最好的实现方式。
我的解决方案对以前的结果使用了适当的缓存（使用闭包的功能），因此，您使用它的次数越多，性能就会越来越好
为了获得前 N 个素数，我遍历 getPrimesTill 直到我达到足够的长度......这里有一个折衷方案，它会找到比第一次预期更多的素数，但我认为它不可能是任何其他方式。也许
getPrimesTill(n + ++count * n * 5)为了能够在避免堆栈溢出的同时处理非常大的数字，我使用 for 循环而不是递归实现了筛选算法。
代码如下：
function Primes() {
let thePrimes = []
const shortCircuitPrimes = until => {
const primesUntil = []
for (let i = 0; ; i++) {
if (thePrimes[i] > until) {
return primesUntil
}
primesUntil.push(thePrimes[i])
}
}
const sieveLoop = n => {
const list = buildListFromLastPrime(n)
const result = []
let copy = [...thePrimes, ...list]
for (let i = 0; i < result.length; i++) {
copy = copy.filter(x => x % result[i] !== 0)
}
for (let i = 0; ; i++) {
const first = copy.shift()
if (!first) return result
result.push(first)
copy = copy.filter(x => x % first !== 0)
}
}
const buildListFromLastPrime = n => {
const tpl = thePrimes.length
const lastPrime = thePrimes[tpl - 1]
const len = n - (lastPrime ? tpl + 1 : 1)
return new Array(len).fill(null).map((x, i) => i + 2 + tpl)
}
const getPrimesTill = n => {
const tpl = thePrimes.length
const lastPrime = thePrimes[tpl - 1]
if (lastPrime > n) {
return shortCircuitPrimes(n)
}
const primes = sieveLoop(n)
if (primes.length - thePrimes.length) {
thePrimes = primes
}
return primes
}
const getFirstPrimes = n => {
let count = 0
do {
if (thePrimes.length >= n) {
return thePrimes.slice(0, n)
}
getPrimesTill(n + ++count * n * 5)
} while (true)
}
return { getPrimesTill, getFirstPrimes, thePrimes }
}
const { getPrimesTill, getFirstPrimes, thePrimes } = Primes()
我为它创建了一个回购协议，通过详尽的测试任何人都想试一试。
https://github.com/andrepadez/prime-numbers-sieve-eratosthenes-javascript
整个测试套件需要大约 85 秒才能运行，因为我正在测试许多可能的组合和非常大的数字。
此外，所有预期结果都是从 Haskell 实现中获得的，因此不会污染测试。
另外，我发现了这个很棒的视频，其中那个人使用 TypeScript 实现了惰性求值和无限列表……最后，他用 Javascript 构建了筛选算法，其工作方式与 Haskell 中的预期完全一样
所有这些生成器都在 prime-lib 中可用了一段时间：
import {generatePrimes, stopOnCount} from 'prime-lib';
const i = generatePrimes(); // infinite primes generator
const k = stopOnCount(i, 10); // the first 10 primes
console.log(...k); //=> 2 3 5 7 11 13 17 19 23 29
import {generatePrimes, stopOnValue} from 'prime-lib';
const i = generatePrimes({start: 1000});
const k = stopOnValue(i, 1100);
console.log(...k); //=> 1009 1013 ... 1093 1097
...等等，库本身有很多例子.
附言我是作者